에라토스테네스 체

에라토스테네스 체

ex)

i*i부터 시작하는 이유!
2*2, 2*3, 2*4, 2*5 - - -
3*3, 3*4 - - -

3*2는 이미 체크를 하였기 때문에 볼필요가 없다.

[-] Collapse

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define MAX_N 200000
// minFactor[i] = i의 가장 작은 소인수 (i가 소수인 경우 자기 자신)
int minFactor[MAX_N], n;

void eratosthenes2() {
    //1은 항상 예외 처리
    minFactor[0] = minFactor[1] = -1;
    //모든 숫자를 처음에는 소수로 표시해 둔다.
    for (int i = 2; i <= MAX_N; ++i)
        minFactor[i] = i;
    //에라토스테네스의 체를 수행한다.
    int sqrtn = int(sqrt(MAX_N));
    for (int i = 2; i <= sqrtn; ++i){
        if (minFactor[i] == i){
            for (int j = i*i; j <= MAX_N; j += i){
                //아직 약수를 본적 없는 숫자인 경우 i를 써 둔다.
                if (minFactor[j] == j)
                    minFactor[j] = i;
            }
        }
    }
}
//2 이상의 자연수 n을 소인수분해한 결과를 반환한다.
vector<int> factor(int v) {
    vector<int> ret;
    //n이 1이 될 때가지 가장 작은 소인수로 나누기를 반복한다.
    while (v > 1){
        ret.push_back(minFactor[v]);
        v /= minFactor[v];
    }
    return ret;
}
int main(){
    int val; cin >> val;
    eratosthenes2();
    vector<int> ans = factor(val);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    return 0;
}