티스토리 뷰
에라토스테네스의 체
수학자 에라토스테네스가 발견한 소수를 찾는 방법입니다. 2의 배수부터 시작 하여 10의 자리 미만 까지 배수를 체크한 후 나머지 체크가 안된 부분이 소수라고 말할 수 있습니다.(소수는 n의 배수가 아니여야합니다.) 다음과 같이 구현이 가능합니다.
첫번째 for문에서 (i*i <= 100)은 이미 증명된 공식에 의해서, 루트 n까지만 나누어서 떨어지면 소수가 아니므로 범위를 줄 일 수 있습니다.(i <= sqrt(100))
반응형