소개
벼룩시장에서 무작위 컴퓨터 부품이 잔뜩 든 큰 상자를 하나 샀어요.
그 부품들을 조립해서 맞춤형 컴퓨터를 만들기 시작했죠.
여러 부품 조합의 성능을 시험해 보고 싶어졌고, 직접 벤치마킹 프로그램을 만들어서 컴퓨터들을 서로 비교해 보기로 했어요.
그래서 선택한 것이 바로 유명한 "에라토스테네스의 체" 알고리즘이에요. 아주 오래된 알고리즘이지만, 컴퓨터를 한계까지 밀어붙일 만한 알고리즘이죠.
지침
여러분의 목표는 주어진 수보다 작거나 같은 모든 소수를 찾기 위해 에라토스테네스의 체 알고리즘을 구현하는 프로그램을 만드는 거예요.
소수는 1보다 큰 수 중에서 1과 자기 자신으로만 나누어지는 수예요.
예를 들어 2, 3, 5, 7, 11, 13은 소수예요.
반면 6은 1과 자기 자신뿐만 아니라 2와 3으로도 나누어지기 때문에 소수가 아니에요.
에라토스테네스의 체를 사용하려면, 먼저 2부터 주어진 수까지의 모든 수를 적어요.
그다음에는 다음 단계를 따라요:
- 표시되지 않은 다음 수를 찾아요(표시된 수는 건너뛰어요).
이 수가 소수예요.
- 그 소수의 모든 배수를 소수가 아님으로 표시해요.
모든 수를 확인할 때까지 이 단계를 반복해요.
마지막에는 표시되지 않고 남은 수가 모두 소수예요.
에라토스테네스의 체는 각 소수의 배수를 표시할 때, 각 수를 나누어 보는 대신 덧셈(소수를 반복해서 더하기)이나 곱셈(소수의 배수를 바로 계산하기)을 사용해요.
테스트는 알고리즘을 구현했는지까지는 확인하지 않고, 올바른 소수를 구했는지만 확인해요.
예시
10보다 작거나 같은 소수를 찾는다고 해봐요.
-
2, 3, 4, 5, 6, 7, 8, 9, 10을 적고, 모두 표시하지 않은 채로 둬요.
2 3 4 5 6 7 8 9 10
-
2는 표시되지 않았으므로 소수예요.
4, 6, 8, 10을 "소수가 아님"으로 표시해요.
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
3은 표시되지 않았으므로 소수예요.
6과 9를 소수가 아님으로 표시해요 (이미 표시된 6은 표시하지 않아도 돼요).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
4는 "소수가 아님"으로 표시되어 있으므로 건너뛰어요.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
5는 표시되지 않았으므로 소수예요.
10을 소수가 아님으로 표시해요 (이미 표시되어 있어서 선택 사항이에요).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
6은 "소수가 아님"으로 표시되어 있으므로 건너뛰어요.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
7은 표시되지 않았으므로 소수예요.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
8은 "소수가 아님"으로 표시되어 있으므로 건너뛰어요.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
9는 "소수가 아님"으로 표시되어 있으므로 건너뛰어요.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
10은 "소수가 아님"으로 표시되어 있고, 더 확인할 수가 없으므로 여기서 멈춰요.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
모든 수를 확인한 결과 2, 3, 5, 7이 아직 표시되지 않은 채로 남아 있고, 이 수들이 10보다 작거나 같은 소수예요.
