algorithm1 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 흔히 에라토스테네스의 체를 사용해 n 이하의 모든 소수를 구하려고 할 때, 효율적으로 구하기 위해 n의 제곱근( sqrt(n) ) 까지만 확인하곤 한다. 1년전쯤엔 n까지 다 확인하거나, 좀 머리 쓴다고 n/2까지 확인했었다. 그런데 당시에 sqrt(n)까지만 본다는 획기적인 말을 들었고, 증명을 찾아봤었다. 증명을 어디서 봤는진 정확히 모르겠다. 아무튼 자주 쓰이다보니 현재까지도 기억하고 있고, 중간중간 블로그에 해설을 적을 때 에라토스테네스가 나올때 마다 작성하기 귀찮아서 따로 글을 쓰게 되었다. 최대한 쉽게 작성해보겠다. n 이하의 모든 소수를 구한다고 해보자. 이 때 해당 수 n은 자연수 a, b에 대해 n = a * b 라고 표현할 수 있다. -> 예를들어 12는 2*6 혹은 3*4 등으로 나타.. 2022. 2. 12. 이전 1 다음
