에라스토테네스의 체

서론

에라스토테네스의 체

코딩 테스트에서 자주 등장하는 알고리즘 중 하나인 '에라스토테네스의 채'를 이용한 소수 찾기 방법에 대해 알아보겠습니다. 이 방법은 특정 범위 내에서 소수를 효과적으로 찾는데 사용됩니다.

---

방법

1. 2부터 시작하여, 특정 수 N까지의 모든 수를 나열합니다.

2. 아직 지워지지 않은 수 중 가장 작은 수를 찾습니다. 이 수는 소수입니다.

3. 그 소수의 배수를 모두 지웁니다.

4. 남아있는 수 중에서 다시 가장 작은 수를 찾고, 이를 반복합니다.

---

예제

#include <iostream>
#include <vector>

int main() {
    int N = 100;  // 소수를 찾을 범위 설정
    std::vector<bool> prime(N + 1, true); // 모든 숫자를 소수로 가정

    // 에라스토테네스의 채 알고리즘 적용
    for (int i = 2; i * i <= N; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= N; j += i)
                prime[j] = false;
        }
    }

    // 소수 출력
    for (int i = 2; i <= N; i++) {
        if (prime[i])
            std::cout << i << " ";
    }
    return 0;
}

설명

 벡터를 사용하여 2부터 N까지의 수에 대해 소수 여부를 저장합니다. 처음에는 모든 수를 소수로 가정하고, 에라스토테네스의 채 알고리즘을 적용하여 소수가 아닌 수의 위치를 false로 변경합니다. 그리고 마지막에는 소수로 남아 있는 숫자들을 출력합니다.

위키피디아