[알고리즘 문제] pfactorization

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        while (num > 1) { // 나누는 대상의 값이 1이면 모두 나누어 떨어졌음을 의미하기 때문에 1보다 커야함
            for (int i = 2; i <= num; i++) { // 2~n까지의 수로 현재 num을 나누어 봄
                if (num % i == 0) { // i번째 숫자가 나누어 떨어지면 이는 소인수(n을 가장 작은 소수부터 시작했기 때문)
                    num /= i; // num을 i로 나눔.
                    System.out.println(i);
                    break;
                }
            }
        }

    }
}

문제는 입력받은 정수를 소인수분해 하는 문제이다. 소인수분해란 자연수를 소인수의 곱으로 나타낸 것을 의미한다. 12라는 수가 있다면 2x6으로 표현한다면 6은 소수가 아니기 때문에 2x2x3으로 소인수 분해를 표현할 수 있다.

 

아이디어는 입력받은 정수(num)가 1보다 클떄까지 while문을 반복한다. 이유는 입력받은 정수가 while문을 반복하면서 소수로 계속 나누어 지는데, 만약 더이상 소수로 나눌 수 없다면 즉 입력받은 정수가 1이 된다면 소인수를 모두 구했으니 while문을 빠져나와야 한다.

 

for문은 2에서 num까지 반복하는데 72를 입력받는다면 i=2일때 if문에서 걸려 72/2을 수행하고 소인수를 출력하고 for문을 빠져나온다. 이런 방법으로 소인수를 계속 찾고 소인수를 모두 찾게되면 num=1이 될 것이다. 그러면 while문을 탈출하게 된다.