에라토스테네스의 체(소수 구하기)

에라토스테네스의 체(소수 구하기)

에라토스테네스의 체

기원전 2세기경 그리스의 수학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법을 일컫는다. 가루를 곱게 치거나 액체를 거르는 데 쓰는 기구인 체로 어떤 물질을 걸러내듯이 여러 차례에 걸쳐서 소수가 아닌 수를 걸러내고 남은 소수를 찾아내는 방법으로 에라토스테네스가 그 방법을 생각해 내었으므로 "에라토스테네스의 체"라고 불려진다. 소수는 규칙이 없다. 그렇다고 수를 한 개씩 소수인가 아닌가를 알아보는 일은 쉬운 일이 아니다. "에라토스테네스의 체"에 의한 방법으로 소수를 찾으면 좀 더 쉽게 찾아낼 수 있다. "에라토스테네스의 체"에 의한 방법으로 1에서 100까지의 자연수 중에서 소수를 찾는 방법은 다음과 같다

설명 및 사진 출처 : 눈높이 대백과

구현 소스

함수명이 정말 맘에 안들지만 일단 그냥 넘어가기로..
위의 설명과 같은 방법으로 코딩을 하였다.

근데 !!! 왜 ! 100까지 for문을 사용하지 않고 sqrt함수를 사용한 것일까 !!

소수는 n의 배수가 아니고
입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다.
그러나 모두 나누어볼 필요없이, 루트 n 까지만 나누어서 떨어지면 소수가 아니다.

예전에 증명된 공식이라지만.. 이 방식을 알았을 때 오오 ~~ 이랬었다.
나중에 비슷한 문제를 응용할 수 있을지 자신이 없다.

힘내자.