에라토스테네스의 체 : 소수가 아닌 것들을 지운다.

 소수를 구할 때 쓰는 알고리즘 중에서, 에라토스테네스의 체 알고리즘이 있습니다. 제가 ps를 하면서 상당히 많이 썻던 것인데요. 결론부터 말씀드리겠습니다. [1,n]까지 해당 알고리즘을 이용해서 훑는 경우에, 시간 복잡도는 O(nlog(logn))입니다. 생각보다 상당히 빠르게 동작한다는 것을 알 수 있어요.

 

 

---

 [1,14]의 범위에 있는 자연수가 소수인지 아닌지 빠르게 훑어봅시다.

 

 

 하늘색은, 아직 visit를 하지 않았다는 의미입니다. 일단 이것이 무엇을 의미하는지 추후에 보도록 합시다. 먼저, 1은 소수가 아니므로, 노란색으로 표시를 합니다.

 

 

 다음에, 2를 봅시다. 2는 하늘색으로 표시가 되어 있으므로, 방문한 녀석이 아닙니다. 그러면 여기서 우리는, 2를 제외한, 2의 배수들을 모두 제거를 할 건데요. 그러면 4, 6, 8, 10, 12, 14가 지워질 겁니다. 지워진 것들을 연두색으로 표시해 보겠습니다.

 

 

 초록색으로 칠해진 부분은 방문을 한 것으로 처리합니다. 왜 그런지는 나중에 보도록 합시다. 다음에 3으로 넘어갑시다. 3으로 넘어갈 건데요. 이 친구 역시 하늘색으로 표시가 되어 있습니다. visit를 하지 않은 것이므로, 3을 제외한 3의 배수를 모두 지웁니다.

 

 

 그러면 6, 9, 12 등이 지워질 겁니다. 다음에 4를 검사해 봅시다.

 

 

 그런데 4는 이미 방문을 해 버렸네요. 왜 방문을 한 상태가 되었을까요? 잠깐 2가 있었던 상황으로 넘어와 보겠습니다. 2를 제외한 2의 배수들을, 보라색으로 칠해 보았습니다.

 

 

 이 단계에서 4가 visit 체크가 됩니다. 즉, 4는 자기 자신과 1이 아닌, 2로 나누어 떨어집니다. 그렇기 때문에, 2의 배수이면서 2가 아닌 수들을 방문 처리 하는 과정에서, 4가 visit 되었다고 된 것입니다. 즉, 4를 검사했을 때에는, 4가 이미 방문이 된 상태였기 때문에, 소수가 아닙니다.

 

 

 다음에 5를 보면 5는 하늘색으로 칠해져 있습니다. 즉 방문하지 않은 상태입니다. 따라서, 5는 소수입니다. 이 때, 5의 배수이면서 5가 아닌 수들을 visit 처리를 합니다. 6은 어떤가요? 이미 노란색으로 칠해졌기 때문에 건너 뜁니다.

 

 

 7은 어떤가요? 탐색을 할 때, 하늘색이기 때문에 소수입니다. 이 때 7이 아니면서 7의 배수인 것을 모두 방문했다는 처리를 합니다. 이런 식으로 2부터 14까지 쭉 돌다보면, visit 처리를 안 한 수는 2, 3, 5, 7, 11, 13임을 알 수 있어요. 이들은 모두 소수임을 알 수 있습니다.

 

 

---

 이제 간단하게 에라토스테네스의 체 알고리즘의 코드를 봅시다. 제가 설명한 대로 구현을 했습니다. 일단, 보시면 p[i]가 0이 아닌 경우는 continue 한 걸로 보아서는, p[i]는 방문 상태를 검사하기 위한 것인가 봅니다. 그리고, 그게 아니라면, 21번째 줄의 for loop를 수행하는데요. i의 배수이면서 i가 아닌 수들을 모두 visit 상태로 만들어 버림을 알 수 있어요.

 

 

 이제 main 함수를 이렇게 작성해 봅시다. 그리고 실행을 해 봅시다. 저는 p[i]가 0인 i값을 모두 출력했는데요. p[i]가 0이라는 의미는, i가 소수라는 것입니다.

 

 

 실행 결과는 위와 같습니다. 만약에 [1,n] 범위 내에 있는 수들을 (n은 적당히 큰 수) 소인수 분해 해야 하는 경우는 이야기가 달라질 수 있는데요. 이 경우는 어떻게 하면 좋을까요? 이 때에는 코드만 바꿔 주시면 됩니다.

 

 

 p[x]를 x를 나누어 떨어지게 하는 소인수 중 하나라고 정의합시다. 그러면 t까지 보았을 때, p[t]의 값이 0이라는 것은 t가 소수라는 것입니다. 그러면, t의 배수인 것들은 소인수로 t를 가지겠네요. 따라서, 요렇게 코딩해 주시면 됩니다. 나머지 부분은, 어떠한 수 k를 k의 소인수로 계속 나눠 가면서, 1이 될 때 까지 나누면 됩니다.