[C++, 템플릿] 소수 구하기(에라토스트네스의 체)

소수 구하기(에라토스트네스의 체)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {

    int N = 10000; // 0 ~10000까지의 소수 구하기
    vector<bool>prime(N + 1, true); // 최종적으로 true일 경우 소수
    
    prime[0] = prime[1] = false;
    for(int i=2; i<=sqrt(N); i++){
        if (prime[i] == true) {
            int k = 2;
            while (i * k <= N) {
                prime[i * k] = false;
                k++;
            }
        }
    }
    
}