[알고리즘] 에라토스테네스의 체 (Swift)

에라토스테네스의 체

에라토스테네스의 체 알고리즘은 고대 그리스 수학자인 에라토스테네스가 만들어낸 소수를 찾는 알고리즘 입니다.
마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 불린다고 하네요.

방법

예를 들어 1 ~ 100까지의 숫자 중 소수를 찾는다고 생각해 봅시다.

1. 먼저, 1부터 100까지의 수를 쭉 써줍니다.

코드상으로는 101만큼의 크기인 Boolean Array를 true로 초기화를 해줬습니다.

표로 나타내보면, 이렇게 나타낼 수 있겠네요.

2. 1은 소수가 될 수 없기에 제거해줍니다.

3. 2를 제외한 2의 배수를 제거합니다.

4. 3을 제외한 3의 배수를 제거합니다.

이제 다음 차례로는 4를 제외한 4의 배수를 제거해야겠죠?
하지만 4는 2의 배수이기 때문에, 이미 다 지워졌습니다.
다음으로는 5를 제외한 5의 배수를 제거해야겠죠?

5. 5를 제외한 5의 배수를 제거합니다.

6. 7을 제외한 7의 배수를 제거합니다.

이 과정을 언제까지 해야할까요..?

굳이 n(100)까지 반복할 필요는 없습니다.

77이란 수는 7 * 11 로 이루어져 있습니다.

7의 배수로서 77이란 수는 이미 지워져버렸기 때문에, 11의 배수를 지울 때, 77은 이미 지워져있겠죠??

그럼 11의 배수들로 지울 숫자는 이미 다 지워져있습니다.
만약 n이 130이라면, 121 (11 * 11)이 최초로 지워지게 되겠네요.

n보다 작은 어떤 수 m이 $m = ab$라면 a, b 중 하나는 $\sqrt{n}$ 이하힙니다.

즉, $\sqrt{n}$보다 작은 수의 배수만 체크해도 전부 지워지기 때문에 $\sqrt{n}$ 까지 반복하면 됩니다.

2, 3, 5 .. 의 배수를 지우는 것을 코드화 하면 이렇게 할 수 있겠군요!

isPrimeNumber[i]가 true인 것들의 인덱스만 출력해주면 소수를 출력할 수 있습니다.

고차함수를 써서 이렇게 작성할 수도 있겠군요!

전체 코드

이번 포스팅에서는 에라토스테네스의 체 알고리즘에 대해 알아보았습니다.
알고리즘 문제를 풀면서 에라토스테네스의 체 알고리즘을 조금 응용하는 문제들도 있더라구요. 꼭 알아둬야할 알고리즘인 것 같습니다.

잘못된 정보가 있으면 지적 부탁드립니다. 😅