에레토스테네스의 체

에레토스테네스의 체 기본 원리

 

n이하의 소수를 구하는 공식에 사용되는 에레토스테네스의 체.

소수와 다르게, 배수로 표현할 수 있는 수는 합성수이다.

에레토스테네스의 체는 소수가 아닌 합성수를 소거하는 방식으로 구하는 방식이다.

 

2를 제외한 짝수들은 모두 합성수이다.

2의 배수로 표현할 수 있기 때문이다.

따라서 n보다 작은 홀수들이 합성수인지를 확인하면 된다.

근데 왜 √n 이하만 반복 조회를 하는 것일까?

 

조회 대상인 n이 아닌 인수(n보다 작은 홀수) 관점에서 보면 그 이유를 알게 된다.

n보다 작은 홀수를 k라고 하자.

k의 거듭제곱은 k x k이다.

즉, k의 거듭제곱은 k의 배수이다.

이 경우, k의 거듭제곱은 합성수이기 때문에 짝수의 경우처럼 조회 대상에서 제외할 수 있다.

 

조회할 인수를 거듭제곱하는 경우와

 '√ 조회 범위' 하는 경우가 동일한 효과를 가지기 때문에

 √n 이하만 반복 조회를 하는 것이다.