[C++] 백준 알고리즘 16563 어려운 소인수분해 (에라토스테네스의 체)

16563번: 어려운 소인수분해 (acmicpc.net)

16563번: 어려운 소인수분해

 

일반 에라토스테네스의 체는 bool 배열을 만들어서 소수면 true, 아니면 false를 저장한다.

그런데 이 문제에서는 소인수들을 찾아야하므로 bool 배열 대신 int 배열을 만들어서,

어떤 수로 인해 소수가 아니게 되었는지를 저장한다.

 

예를 들어 8의 경우, 8은 2의 곱으로 인해 소수가 아니게 되었다. >> 2 출력

8/prime[k] = 8/2 =4 가 된다. 4는 2의 곱으로 인해 소수가 아니게 되었다. >> 2 출력

4/prime[k] = 4/2 =2 가 된다. 2는 소수이다. >> 2 출력 , 종료

 

결과적으로 8의 경우에는 2 2 2 가 출력된다.

 

#include<iostream>
#include<vector>

using namespace std;

const int SIZE = 5000000;

vector<int> is_prime(){
    vector<int> prime(SIZE+1,0);
    int i,j;

    //각 수의 모든 소인수를 자기 자신으로 초기화
    for(i=2;i<SIZE+1;i++)
        prime[i]=i;

    //에라토스테네스의 체 이용
    for(i=2; i*i<SIZE+1; i++){ // i <= 루트 SIZE 까지 라고 해도 ok
         if(prime[i]==i){ //소수의 배수를 지울 것임. 소수인 것 고르기
             for(j=i*i; j<SIZE+1; j+=i){ //i*i인 이유 =
                 // 50의 경우, 50*1 ~ 50*49는
                 // 1의 배수 ~ 49의 배수를 지웠을 때 이미 지워짐
                 //그러므로 50*50 부터 50*51 순으로 확인함
                 if(prime[j]==j){ //소수가 자기 자신인 경우, 즉 지워지지 않은 수들
                     prime[j]=i;
                 }
             }
         }
    }
    return prime ;
}

int main() {
    //입출력 속도 향상
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,k;
    cin>>n;

    //모든 수 마다 최소 소수를 저장
    vector<int> prime = is_prime();

    while(n--){
        cin>>k;
        while(k>1){ //소인수 계속 출력
            cout<<prime[k]<<' '; // 예를 들어 4의 경우 소인수 2가 출력됨
            k/=prime[k]; // k = 4나누기 (소인수)2 = 2가 됨.
            // while 한 번 더 돌고 k = 2가 출력 되고 K=1이 되고 while 종료
            //최종적으로 4의 경우, 2 2 가 출력됨
        }
        cout<<'\n';
    }
}