[C++] 에라토스테네스의 체

에라토스테네스의 체란 무엇일까?

 

소수를 판단할 때 유용하게 쓰인다.

소수란 1과 자기자신으로만 나누어지는 수이다. 2 3 5 7... 등이 있다.

 

2부터 생각을 해보자. 2는 소수이다. 2*n배는 소수가 아니다. 그렇다면 2*2, 2*3, 2*4.... 2*(n) 은 모두 소수가 아니므로 제거한다. (코드에서는 bool형 배열을 false함으로써 제거)

그리고 3도 같은 방법으로 3의 배수들을 false한다.

4의 경우 이미 2*2에서 false되었으므로 5를 확인한다.

 

이런식으로 계산을하면 소수 2 3 5 7..은 남아있고, 소수가 아닌 어떤 수들의 배수들인 4 5 8 9 10... 은 false처리되며 제거된다.

 

이 방법으로 소수 판정을 하면 O(nlog(log n))만에 가능하다.

---

false로 바꿔주면서 루트 n까지만 반복문을 도는데 그 이유는 무엇일까?

 

소수 검사를 할 때 2,3,5.... 101 직전까지 검사를 했다 하자.
101에 대해 검사를 하려고 할 때, 101*2, 101*3... 101*100 은 이미 앞에서 검사를 했다.
그러므로 101*101, 101*102... 부터 검사하면 된다. (검사란 소수가 아닌 것을 false로 바꾸는 것을 의미)
이때 101*101이 n보다 크다면 검사하지않아도 되기 때문에
루트 n까지만 검사하는 것이다.
   

결론적으로 루트n 까지 검사해도,

루트 n에 대해 (for문에서) i*i할 시점에 (루트n) * (루트n) = n 이라는 계산이 되므로, 루트n까지만 검사를 해도 n이 소수인지 아닌지 판단된다.

 

 

 

 

 

 

[C++] 백준 알고리즘 6588 골드바흐의 추측 (에라토스테네스의 체) (tistory.com)

[C++] 백준 알고리즘 6588 골드바흐의 추측 (에라토스테네스의 체)