[Algorithm] 알고리즘 준비 04. 소수, 에라토스테네스의 체

소수

소수란?

2나 3과 같이 1과 자신의 수에 의해서만 나누어 떨어지는 수, 또는 2개의 약수만 가지는 수.

모든 자연수는 소수의 곱으로 표현된다.

에라토스테네스의 체

N까지의 숫자가 있다면, 소수의 배수를 순서대로 제거하는 방법

- 1부터 N까지의 수를 배열

- 2는 소수이기 때문에 남겨두고, 2의 배수를 모두 제외 시킴

- 3는 소수이기 때문에 남겨두고, 3의 배수를 모두 제외 시킴

- 다음 수는 4이지만, 이미 2의 배수라 제외 되었음.

- 5는 소수니 남겨두고 5의 배수 모두 제외

...

...

...

- N이 제외된 수가 아니면 N은 소수이며 N의 배수를 모두 제외

해당 방법으로 N 까지 진행한다.

N 까지의 소수를 찾는 법

#include <iostream>
 
using namespace std;
bool prime[10001];
 
int main() {
 
    for (int i = 2; i <= 10000; i++)
    {
        if (prime[i] == false)
        {
            for (int j = i * i ; j <= 1000 ; j += i)
            {
                prime[j] = true;
            }
        }
    }
    
    for (int i = 2; i < 10000; i++)
    {
        if (prime[i] == false)
        {
            printf("%d ", i);
        }
    }
}