Algorithm | 에라토스테네스의 체

소수의 개수를 세는 알고리즘 문제를 풀다가 효율성 검토에서 계속 실패를 해서 다른 답안을 찾게 되었다. 대량의 소수를 판별하는 방법으로 에라토스테네스의 체 알고리즘을 이용하면 똑같이 for문을 이용하더라도 효율성 검토를 통과할 수 있다.

에라토스테네스의 체

소수가 아닌 1은 제외하고 2부터 소수인지 판별을 한다. 2는 1과 자신외에 나눌 수 있는 수가 없으므로 소수이고, 판별하고자 하는 수까지 모든 2의 배수를 지운다. 3, 5, 7도 마찬가지로 배수들을 지워나가며 소수를 구할 수 있다.

아래 그림의 경우 11^2 >120이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다. 이러한 논리로 대량의 소수를 구할 때는 제곱근을 이용하여 빠르고 쉽게 소수를 구할 수 있다.

[참고]
위키백과_에라토스테네스의 체