[수학] 에라토스테네스의 체

가끔 알고리즘 문제를 풀다보면

소수(prime number)와 관련된 문제를 만나게 됩니다

백준 6588번 문제를 해결하는 과정에서

관련 개념으로 에라토스테네스의 체에 대해서 찾아보게 되었습니다

에라토스테네스의 체

에라토스테네스의 체는 n이 1000만보다 작을 때

n보다 작은 소수를 찾는 가장 효율적인 방법 중 하나입니다

n = 100일 때를 예로 들어보겠습니다

1. 2부터 100까지의 숫자 목록을 만든다

2. 2로 나누어 떨어지고 2의 제곱보다 크거나 같은 모든 숫자를 표시한다

3. 이제 표시되지 않은 다음 숫자 3으로 넘어가서
   3의 배수이고 3의 제곱보다 크거나 같은 모든 숫자를 표시한다

4. 다음 표시되지 않은 숫자 5로 넘어가서 5의 배수 중 제곱보다 크거나 같은 모든 수를 표시한다

5. 다음 표시되지 않은 숫자 7로 넘어가서 7의 배수 중 제곱보다 크거나 같은 모든 수를 표시한다

6. 이 과정을 계속하면 최종 표는 아래와 같다

전체 과정에서 매번 표시되지 않은 숫자가

소수에 해당하게 됩니다

이러한 방법으로 소수를 찾을 수 있습니다

이 개념을 잘 기억해놓았다가 적절한 문제에 잘 활용할 수 있기를..!

참고자료

Sieve of Eratosthenes