[기본] 에라토스테네스의 체 (소수찾기)

소수는 1과 자기 자신만을 약수로 가지는 수이다. 1은 소수가 아니다.

에라토스테네스의 체를 이용해서 소수를 찾는 방법

1. 2부터 n까지의 모든 수를 나열한다.

2. 2는 소수이므로 소수로 입력한다. 이후 2의 배수들은 소수가 아니므로, n까지의 2의 배수는 모두 지운다.

3. 3은 소수이므로 2와 똑같이 3의 배수는 모두 지워준다.

4. 4는 2의 배수이므로 지워졌으므로 해당 사항X

5. 5는 소수이고 지워지지 않았기 때문에 5의 배수를 모두 지워준다.

6. 계속 반복한다.

 

 

n이하의 모든 수로 각각 나누어 보는 방법보다 훨씬 속도가 빠르다.