[기초 수학] 소인수분해

 

 

📌 소인수분해

- 주어진 자연수를 그 수를 나누는 소수들의 곱으로 분해하는 작업

- 예) \[ 60 = 2 \times 2 \times 3 \times 5 \]

1) 2로 나누어질 수 있을때까지 나눈다.

2) 그 이후 홀수부터 계속해서 나눈다.

3) 반복문이 끝나고 남은 값이 1보다 크면 그 값 자체가 소수임으로 출력.

public class PrimeFactorization {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        sc.close();

        System.out.println("결과");
        primeFactorization(n);
    }

    public static void primeFactorization(int n){
        if(n < 2){
            System.out.println("2 이상의 자연수를 입력하세요");
            return;
        }

        while(n % 2 == 0){
            System.out.println(2 + " ");
            n /= 2;
        }

        for(int i = 3; i * i <= n; i += 2){ //홀수만 체크
            while(n % i == 0){
                System.out.println(i + " ");
                n /= i;
            }
        }

        //남은 소수가 있다면 출력
        if(n > 1){
            System.out.println(n);
        }
    }
}