[알고리즘] 에라토스테네스의 체

◼ 원리

임의의 수 N까지의 소수를 구하고자 할 때 2부터 N의 제곱근까지 돌며
i의 모든 배수들을 소수에서 제외시키는 방식이다.

◼ 해결

크기가 N+1인 배열을 하나 준비한다. (arr[i] = i)
i = 2 ~ sqrt(N)까지 돌며 i의 배수들을 모두 0으로 바꿔준다. (primeNum[i]==0인 경우엔 이미 소수가 아니므로 pass)

◼ C/C++ 소스 (N까지의 소수 개수 구하기)

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N, num = 0; cin >> N;

    int* primeNum = new int[N+1];

    for (int i = 2; i <= N; i++) primeNum[i] = i;

    for (int i = 2; i <= sqrt(N); i++) {
        if (primeNum[i] == 0)continue;
        for (int j = i * i; j <= N; j += i) {
            primeNum[j] = 0;
        }
    }

    for (int i = 2; i <= N; i++) {
        if (primeNum[i] != 0)num++;
    }

    cout << num;
    
    delete[] primeNum;
    
    return 0;
}