[Baekjoon/C++] 소인수분해 11653번

Baekjoon Online Judge 

문제로 이동

 

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

 

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

---

예제 입력	예제 출력
72	2 2 2 3 3
3	3
6	2 3
2	2
9991	97 103

---

풀이

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int N, num;
    cin >> N;

    // N이 10보다 같거나 크면 제곱근을 구한다.
    if (N < 10) 
        num = N;
    else
        num = sqrt(N);

    // 2부터 N 혹은 N의 제곱근까지의 숫자 중에서 소수를 찾는다.
    for (int i = 2; i <= num; i++) {
        for (int j = 2; j <= i; j++) {
            // 소수를 찾으면 출력
            if (j == i) {
                while (N % i == 0) {
                    N /= i;
                    printf("%d\n", i);
                }
            }
            else if (i % j == 0) break; // 소수는 자기자신과 1만으로만 나누어 떨어져야한다.
        }
    }

    // 제곱근보다 큰 소수 출력
    if(N != 1)
        printf("%d\n", N);

    return 0;
}

전의 포스트처럼 끝까지 for문을 돌리면 시간초과가 발생한다.

숫자 n을 36이라고 할때 이를 곱셈으로 표현할 수 있는 수는 (1, 36), (2, 18), (3, 12), (4, 9) , (6, 6)으로 36의 제곱근인 6까지의 숫자인 1, 2, 3, 4, 6을 찾으면 그 숫자들의 짝인 9, 12, 18, 36을 찾을 필요가 없어진다. 그러므로 위의 코드에서 제곱근을 사용하여 실행 시간을 줄였다.