소수

[Algorithm] 에라토스테네스의 체, 소수찾기 feat. Java

소수(Prime Number) 소수란 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자의 곱(2×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 에라토스테네스의 체 소수를 빨리 찾을 수 있는 알고리즘이다. 과정 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 자기 자신을 제외한 2의 배수를 모두 지운다. 자기 자신을 제외한 3의 배수를 모두 지운다. 자기 자신을 제외한 5의 배수를 모두 지운다. 자기 자신을 제..