에라토스테네스의 체(get Prime Number)

소수를 구할때 최대로 효율적인 알고리즘을 만드는데 도움이 되는 것인데, 따로 개념을 설명하지는 않겠다.

내가 보기 위한 메모용 글이다.

#include<iostream>
#include<math.h>
#include<time.h>
 
using namespace std;
 
#define MAX 50001
 
int num[MAX];
 
void func(int n){
    int sqt = sqrt(n);
 
    for(int i=2; i<=sqt;i++){
 
        if(num[i] == 0) continue;
 
        for(int j=2*i;j<=n;j+=i){
            num[j] = 0;
        }
    }
}
 
int main(){
 
    clock_t start,end;
    int n;
 
    cin >> n;
 
    for(int i=2;i<=n;i++) num[i] = i;
 
    start = clock();
    func(n);
    end = clock();
 
    for(int i=2;i<=n;i++){
        if(num[i] != 0) cout << num[i] << "\n";
    }
 
    cout << (double)(end-start) / CLOCKS_PER_SEC << "\n";
}