소수 구하기

에라토스테네스의 체

소수는 자기 자신과 1만을 약수로 가지는 수이다.
에라토스테네스의 체는 많은 수의 소수판별을 할 때 유용하다.
이 알고리즘은 해당 수가 소수일 때, 해당 수의 배수들은 모두 해당 수를 약수로 가지고 있으므로 소수가 되지 못한다.

1) 낮은 수부터 소수 찾기 시작( ex 2 )
2) 소수 판별
3) 판별한 소수의 배수들을 모두 지운다.

처음 입력한 값 + 1의 크기를 갖는 boolean 배열을 static 배열로 선언한 prime에 대입
0과 1은 소수가 아니기에 prime[0]과 prime[1]에 true를 넣는다.
(true == 소수가 아님, false가 소수)

i 가 2이면 2를 제외한 2의 배수를 모두 지운다.
i 가 3이면 3을 제외한 3의 배수를 모두 지운다.
i 가 4일 때 이미 i 가 2일때 지워 졌으므로
if(prime[i] == true) {continue;}에서 넘어간다.

실행