[에라토스테네스의 체] - BOJ_1929 : 소수 구하기

소수를 판별하는 알고리즘 중에는 굉장히 유명한 에라토스테네스의 체라는 알고리즘이 존재한다.

소수 판별 문제는 대부분 이 알고리즘으로 풀기 때문에 잘 익혀두면 큰 도움이 된다.

오늘 풀어볼 문제인 boj 1929 번 문제다.

 

💡에라토스테네스의 체란?

1. 배열을 원하는 범위만큼 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. 이때, 자기 자신은 지우지 않고,
   이미 지워진 수인 경우 건너뛴다.
3. 지워지지 않은 테이블이 소수로 판별된 테이블이다.

위 예시는 2의 배수를 모두 지우고, 3의 배수를 지우는 과정이다. 이런 식으로 $N/2$까지 진행하고 남은 테이블을 확인한다.

❓에라토스테네스의 체의 시간복잡도

naive한 방법으로는, 일반적으로 어떤 정수의 소수를 판별할때는 2부터 판별 수의 제곱근까지, 판별 수의 약수인지 확인해주는 방식이 있다. 이렇게 할 경우 N개의 수를 모두 소수판별을 할때, 이는 $O(N^{3/2})$의 시간 복잡도를 가진다.

그렇지만, 에라토스테네스의 체를 활용하면 $O(N*{log^{log^N}})$의 시간복잡도를 가진다.

N이 클때 이는 꽤나 큰 시간복잡도 차이를 가지게 된다.

 

📜CODE

#include <bits/stdc++.h>

using namespace std;

int n,m;
int isNotPrime[1010100];


void primeNumber(){
    for(int i=2; i<1010100; i++){
        if(isNotPrime[i]) continue;
        for(int j=i*2; j<1010100; j+=i){
            if(isNotPrime[i]) continue;
            isNotPrime[j]=1;
        }
    }
    return;
}

int main(){
    cin.tie(0)->ios::sync_with_stdio(0);
    cin>>n>>m;
    primeNumber();
    isNotPrime[1]=1;
    for(int i=n; i<=m; i++){
        if(!isNotPrime[i]) cout<<i<<'\n';
    }
}