에라토스테네스의 체 (Sieve of Eratosthenes)

에라스토테네스의 체의 원리

에라스토테네스의 체는 특정 숫자 ( n )까지의 모든 소수를 찾는 고전적인 알고리즘입니다. 이 방법이 ( sqrt(n) )까지의 소수만 확인하는 이유는 수학적 원리에 근거합니다. 간단히 말해, ( n )의 가장 작은 소수인 약수가 ( sqrt(n) )보다 클 수 없기 때문입니다. 아래에서 이를 자세히 살펴보겠습니다.

증명

소수 판별을 위해 숫자 ( n )이 주어졌다고 가정합시다. ( n )이 소수가 아니라면, ( n = a * b )로 표현될 수 있어야 하며, 여기서 ( a )와 ( b )는 1과 ( n ) 자신을 제외한 ( n )의 약수입니다.

만약 ( a )와 ( b ) 둘 다 ( sqrt( n ) )보다 크다면, ( a * b )는 ( n )을 초과하게 됩니다. 왜냐하면:

[ a > sqrt( n ) ] [ b > sqrt( n ) ]

위 두 식을 곱하면:

[ a * b > sqrt( n ) * sqrt( n ) = n ]

이는 ( n = a * b )라는 가정과 모순됩니다. 따라서, 만약 ( n )이 소수가 아니라면 ( a ) 또는 ( b ) 중 적어도 하나는 ( sqrt( n ) ) 이하이어야 합니다.

따라서 ( n )의 소수 여부를 판별하기 위해서는 ( sqrt( n ) ) 이하의 모든 소수로 나누어 봄으로써 충분합니다. 만약 ( n )이 ( sqrt( n ) ) 이하의 어떤 소수로도 나누어지지 않는다면, ( n )은 소수입니다. 반대로, ( n )이 ( sqrt( n ) ) 이하의 어떤 소수로 나누어진다면, ( n )은 합성수입니다.

예제

51이 소수인지 판별하기 위해서 Math.sqrt(51)까지만 확인하면 된다.

long n = 51;
 
isPrime(long n) {
    for (long i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}