백준 알고리즘 11653번 - 소인수분해

에라토스테네체를 통해 소수가 아닌 수를 다 걸러내고 작은 소수 부터 나눠가면서 소인수분해를 진행한다.

 

에라토스테네스의 채란 ?

 

채로 거르듯이 범위내에서 소수가 아닌 수를 골라내는 방법으로 소수를 찾는다.

모든 수로 나눠보는 것보다 훨씬 빠르다. (모든 수로 나눌경우 O(N) = N^2, 에라토스테네스의 채를 사용할 경우 O(N)=N log(logN).

사실상 log(logN)는 1과 비슷하므로(n이 백만이라고 쳐도 1이 조금 안된다!), 엄청나게 빠른 알고리즘이다.

 

for(int i=2;i<=a;i++){
    for(int j=i+i;j<=a;j+=i){
        if(arr[j]==0) continue;
        arr[j]=0;
    }
}

소스코드는 이런 식으로 구현이 가능하다.

 

소수를 구했다면, 이제 약수를 구해야한다.

오름차순이므로 작은 것부터 나눠서, 나눠지면 해당 소수를 프린트해주자.

 

설명이 조금 장황하지만, 소스코드를 보면 이해가 될 것? 같다ㅎㅎ

 

 

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main() {
    int a;
    cin>>a;
    int arr[10000001];
    // your code goes here
    for(int i=1;i<=a;i++){
        arr[i]=i;
    }
    for(int i=2;i<=a;i++){
        for(int j=i+i;j<=a;j+=i){
            if(arr[j]==0) continue;
            arr[j]=0;
        }
    }
    while(a!=1){
    
        for(int i=2;i<=a;i++){
            if(a%i==0) {
                cout<<i<<endl;
                a=a/i;
                break;
            }
        }    
    }
    return 0;
}