소수 판별법 - 에라토스테네스의 체

공간 복잡도 O(N)

 

시간 복잡도 O(NloglogN)

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

bool check[1000005];

int main() {
    for (int i = 2; i * i <= 100000; i++)
    {
        if (check[i])
            continue ;
        
        for (int j = (i * 2); j <= 100000 ; j += i)
            check[j] = true;
    }
    
    for (int i = 2; i <= 100000; i++)
    {
        if (!check[i])
            printf("%d\n", i);
    }
    
    return 0;
}