[알고리즘] 10. 소인수분해

소인수분해

• n = a^x * b^y꼴로 표현하는 프로그램을 작성하시오.

문제 분석

• 36 = 2^2 * 3^2 = 4 * 9

• 짝수는 2의 배수 : 4, 6, 8 등의 수로 인수분해 할 필요가 없음 : continue 사용

• 홀수의 경우 : 9, 25, 49 등의 경우 : 이미 수를 1씩 늘려가며 계속 나눌 것이기 때문에 거듭제곱은 알아서 나누어질 수 있음

• 나눌 수가 1이 되면 종료

코드 작성 - Sampling, Moduling

package algo;

public class Pf01 {
    public static void main(String[] args) {
        // 1. Sampling : 36을 소인수분해하여 나타내시오.

        // 2. Hard Coding : 특징 찾기 1 - 나머지가 0이면 그 수로 계속 나누어지는지 확인
        // 2. Hard Coding : 특징 찾기 2 - 나머지가 0이 아니고 나눌 수가 1이 아니면, 나누는 수 + 1
        // 2. Hard Coding : 특징 찾기 3 - 나머지가 0이 아니고 나눌 수가 1이면, 소인수 분해 종료

        // 3. Moduling
        // 3-1. 나눌 수 N
        int N = 36;
        // 3-2. 소인수분해 시작할 수 a = 2
        int a = 2;

        // 3-3. 결과 Output - N = a*a*a*....
        System.out.print(N + " = ");

        // 3-4. 조건이 맞을때까지 무한 반복 : 조건반복문 while 사용
        while (true) {
            // 소인수가 2보다 커졌을 때의 짝수 : 비교할 필요 없음 : continue
            if (a % 2 == 0 && a != 2) continue;
            // 나머지가 없을 때 : 소인수 분해가 가능할 때
            if (N % a == 0) {
                // N = a : 마지막 소인수 분해
                if (N == a) {
                    System.out.println(a);
                    N = N / a;
                } else {
                    System.out.print(a + " * ");
                    N = N / a;
                }
                // N == 1이면 더 이상 소인수 분해가 불가 : break
            } else if (N == 1) break;
                // 나머지가 있을 때 : 소인수 분해가 불가능 : a + 1
            else a++;
        }
    }
}