c++ 소수 구하기

에라토스테네스의 체를 사용하면 소수를 빠르게 구할 수 있습니다

 

에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘 사용:

• sqrt를 매번 계산하는 대신, 전체 범위에서 소수를 빠르게 구할 수 있습니다.

• 이 알고리즘은 배수 제거 방식으로 소수를 효율적으로 찾습니다.

 

에라토스테네스의 체를 이용한 소수 찾기

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    const int MAX_N = 1000000;
    vector<bool> is_prime(MAX_N + 1, true); // 초기에는 모든 수가 소수라고 가정
    is_prime[0] = is_prime[1] = false; // 0과 1은 소수가 아님

    // 에라토스테네스의 체로 소수 판별
    for (int i = 2; i * i <= MAX_N; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAX_N; j += i) {
                is_prime[j] = false; // i의 배수는 소수가 아님
            }
        }
    }

    // 소수 출력
    for (int t = 2; t <= MAX_N; t++) {
        if (is_prime[t]) cout << t << ' ';
    }

    return 0;
}

깨달은점

for(int j = i * i ... ) 에서 왜 j 를 i * i 로 초기화 하는지 의문이였습니다.

이유는 i는 소수이기에 is_prime 으로 소수를 추가하지 않고 i 의 배수들만 소수로 저장합니다.