[소수]백준 11653 소인수분해

백준11653번

우선 소인수분해가 무엇인지 생각해보았다. 소인수분해는 모든 양의 정수가 소수들의 곱으로 표현되는 것이다. 따라서 가장 처음에 생각했던 것은 우선 입력으로 주어지는 수까지의 소수를 모두 구한 후, 가장 작은 소수 (2) 부터 시작하여 입력으로 주어진 수를 나눈다.

이 때 중요한 것은, 각 소수로 나눌 수 있을 때까지 계속해서 나눠야 한다는 것이다.

해당 수까지의 소수를 구하는 방법은 에라토스테네스의 체를 이용했다.

그리고, 2부터 시작해 나눌 수 있는 만큼 나누고 다음 소수로 옮겨간다.

이 방법에 대한 구현은 다음과 같다.

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int num;
    cin >> num;

    vector<int> prime(num+1,0);
    for(int i=2;i<=num;i++){
        if(prime[i]==0){
            for(int j=2;j<=sqrt(i);j++){
                if(i%j==0){
                    prime[i] = 1;
                    break;
                }
            }
        }
    }
    for(int i=2;i<=num;i++){
        // if Prime!
            if(num % i == 0){
                cout << i << "\n";
                num /= i;
                i--;
            }
    }
}

이 방법은 정답을 알려주지만, 소수를 구하는 과정, 즉 에라토스테네스의 체의 과정에서 시간 초과가 발생한다. (입력의 크기가 1≤N≤10,000,000 이기 때문이다.)

그런데 생각해보니, 2부터 시작해 각 수마다 나눌 수 있는만큼 최대로 나눈다면 그 수의 배수로는 나눠질 수 없게 되기 때문에 굳이 소수를 구할 필요가 없었다.

예를 들어, 2로 나눌 수 있는만큼 나누고 3으로 나눌 수 있는 만큼 나누면, 4로 나눠야 할 때는 이미 2로 나눠진 상태이기 때문에 (4는 2의 배수이기 때문에) 신경 쓸 필요가 없게 되고 결국 소수로 나누는 것과 같은 결과가 나온다. 따라서 위의 코드에서 에라토스테네스의 체 부분을 주석 처리를 하게 되면…시간 초과가 나오지 않게 된다.

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int num;
    cin >> num;

    // vector<int> prime(num+1,0);
    // for(int i=2;i<=num;i++){
    //     if(prime[i]==0){
    //         for(int j=2;j<=sqrt(i);j++){
    //             if(i%j==0){
    //                 prime[i] = 1;
    //                 break;
    //             }
    //         }
    //     }
    // }
    for(int i=2;i<=num;i++){
        // if Prime!
            if(num % i == 0){
                cout << i << "\n";
                num /= i;
                i--;
            }
    }
}