[정수론] 에라토스테네스의 체 (C++)

완전탐색 하지 않고 빠르고 정확하게 소수를 구하는 알고리즘

 

bool visit[MAX] 

-> 2부터 시작하여 소수를 구하고, 소수의 배수를 모두 true 처리를 한다.

-> visit[i]가 0인 인덱스들이 소수이다.

 

 

4,000,000까지 수 중 소수의 개수는 대략 28만 개가 넘는다. 범위에 조심하자!

 

void sieveOfEratosthenes(){
    for(int i=2;i<=sqrt(N);i++){
        if(visit[i]==1) continue;

        for(int j=i+i;j<=N;j+=i){
            visit[j]=1;
        }
    }

    for(int i=2;i<=N;i++){
        if(visit[i]==false) {
            prime.push_back(i);
        }
    }
}

prime=[True]*10000000

def primeChae(n):
    N=10**n
    prime[0]=prime[1]=False
    for i in range(2,int(math.sqrt(N))+1):
        if prime[i]==0: continue
        for j in range(i+i,N,i):
            prime[j]=False

시간복잡도 : O(n log(logn))

 

 

관련 문제

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합