백준 JAVA 11653번 소인수 분해

블로그 이전, 2023. 5. 9. 21:19  에 작성했던 글입니다.

1.나의 풀이

소인수 분해는 소수로 나누면 된다.

처음에는 그럼 소수를 먼저 다 구해야하나? 라고 생각했다. 안 그래도 된다.

아래처럼 코드를 작성하면 소수가 아닌수를 제거할 수 있다. 결국 소수로만 소인수 분해를 할 수 있다.  

 

for (int i = 2; i <= num; i++) {
            while (num % i == 0) {
                num = num / i;
                System.out.println(i);
            }

while문을 반복하면서 합성수(소수가 아닌 수)들은 알아서 걸러진다.

합성수는  소수X어떤 수 로 이루어져있는데 합성수보다 소수가 먼저일 수밖에 없기 때문에 소수가 먼저 while문을 돌면서 다 나눠질 것이다. 예를 들어 8 생각해보면 2*2*2이기 때문에 2에서 다 계산될 수 밖에 없다. 8까지 갈 수 없다. 그래서 합성수까지 안 간다. 가더라도 소수가 다 털린 상태이기 때문에 while문 조건식이 true가 뜰 수 없다.

 

2.나의 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int num = Integer.parseInt(br.readLine());
        prime(num);
        br.close();
    }

    public static void prime(int num) {

        for (int i = 2; i <= num; i++) {
            while (num % i == 0) {
                num = num / i;
                System.out.println(i);
            }

        }
    }

}