체

지침

주어진 수 이하의 모든 소수를 찾는 프로그램을 만드는 것이 과제예요. 이 프로그램은 에라토스테네스의 체 알고리즘을 구현해야 해요.

소수는 1보다 큰 수 중에서 1과 자기 자신으로만 나누어떨어지는 수예요. 예를 들어 2, 3, 5, 7, 11, 13은 소수예요. 반대로 6은 소수가 아니에요. 1과 자기 자신뿐만 아니라 2와 3으로도 나누어떨어지기 때문이에요.

에라토스테네스의 체를 사용하려면, 먼저 2부터 주어진 수까지의 모든 수를 목록으로 만들어요. 그다음에는 다음 단계를 반복해요:

1. 목록에서 표시되지 않은 다음 수를 찾아요 (표시된 수는 건너뛰어요). 이 수가 소수예요.
2. 그 소수의 모든 배수를 소수가 아니라고 표시해요.

목록의 모든 수를 확인할 때까지 이 단계를 계속 반복해요. 끝나면 표시되지 않은 수는 모두 소수예요.

예시

10 이하의 소수를 찾는다고 해봐요.

• 2, 3, 4, 5, 6, 7, 8, 9, 10을 나열하고, 모두 표시하지 않은 상태로 둬요.
• 2는 표시되지 않았으므로 소수예요. 4, 6, 8, 10을 "소수 아님"으로 표시해요.
• 3은 표시되지 않았으므로 소수예요. 6과 9를 소수 아님으로 표시해요 (6을 표시하는 건 선택 사항이에요. 이미 표시되어 있으니까요).
• 4는 "소수 아님"으로 표시되어 있으니 건너뛰어요.
• 5는 표시되지 않았으므로 소수예요. 10을 소수 아님으로 표시해요 (선택 사항이에요. 이미 표시되어 있으니까요).
• 6은 "소수 아님"으로 표시되어 있으니 건너뛰어요.
• 7은 표시되지 않았으므로 소수예요.
• 8은 "소수 아님"으로 표시되어 있으니 건너뛰어요.
• 9는 "소수 아님"으로 표시되어 있으니 건너뛰어요.
• 10은 "소수 아님"으로 표시되어 있으니, 더 확인할 수가 없어서 멈춰요.

모든 수를 확인한 결과 2, 3, 5, 7이 아직 표시되지 않은 채로 남아 있어요. 이 수들이 10 이하의 소수예요.

---

출처

Wikipedia의 에라토스테네스의 체