에라토스테네스의 체

Description

에라토스테네스의 체는 소수를 판별하는 알고리즘이다.
소수란, ‘약수를 두개만 가지는 자연수’를 의미하며 2, 3, 5, 7, 11, … 등이 있다.
이 소수들을 빠르게 구하는 방법이 에라토스테네스의 체이다.

---

Cord

#include <iostream>

using namespace std;

// 1부터 100000까지의 소수 구하기
int number = 100000;
int arr[100001];

void PrimeNumbers()
{
    // 2부터 시작해서 배수가 되는 숫자들을 모두 지운다.
    for (int i = 2; i <= number; i++)
    {
        // 이미 지워졌으면 건너뛰기
        if (arr[i] == 0) { continue; }

        // j = i의 배수를 찾아 지우기
        for(int j = i + i; j <= number; j += i)
        {
            arr[j] = 0;
        }
    }
}

int main()
{
    // arr[idx]에 idx값 대입
    for (int idx = 2; idx <= number; idx++)
    {
        arr[idx] = idx;
    }

    // 에라토스네테스의 체 실행
    PrimeNumbers();

    // 결과 출력
    for (int idx = 2; idx <= number; idx++)
    {
        if (arr[idx] != 0) 
        {
            cout << arr[idx] << ' ';
        }
    }

    return 0;
}

---

Result