에라토스테네스의 체

정의

정 범위안에서 소수를 찾는 방법이다.

 

알고리즘

1. 특정 범위 안의 수 중 가장 작은 소수의 배수를 모두 제외시킨다.

2. 특정 범위 안의 수 중 그다음으로 작은 소수의 배수를 모두 제외 시킨다.

3. 2번의 과정을 반복적을 진행하고 나면 특정 범위 안의 소수가 남는다.

 

특징

특정 범위가 480이라고 가정하면

22^2 > 480 이므로 22보다 작은 수의 배수들만 지원도 충분하다.

 

참고 자료 1 : ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전