[Algorithm] 에라토스테네스의 체, 소수 판정시 제곱근까지 확인하는 이유(python)

에라토스테네스의 체

 

소수를 구할때 많이 사용되는 에라토스테네스의 체를 알아보겠습니다.

 

소수를 구하는 첫번째 방법으로는 모든 숫자를 1에서부터 원하는 수 n까지 완전 탐색으로 소수를 찾아주는 방법이 있습니다. 가장 확실한 방법이지만 시간이 많이 걸린다는 단점이 있습니다.

 

n까지의 소수를 구하는 코드 : 시간복잡도(O²)

def PrimeNumber(n):
    res = []
    for i in range(2, n+1):
        check = True
        for j in range(2, i):
            if i % j == 0:
                check = False
                break
        if check:
            res.append(i)
    return res

 

완전탐색을 사용해서 하나하나 모든 수를 체크해주는 방법입니다.

 

에라토스테네스의 체는 소수를 구하는데 시간을 단축시켜줍니다. (체로 거르는것 같아서 에라토스테네스의 체라고 부릅니다.)

 

에라토스테네스의 체 실행과정. 출처(위키백과)

 

n까지의 소수를 구하는 코드(n = 100)

import math
def PrimeNumber(n):
    chk = [True]*(n+1)
    res = []
    chk[0], chk[1] = False, False
    m = int(math.sqrt(n))
    for i in range(2, m+1):
        if chk[i]:
            res.append(i)
            j = 2
            while i*j <= n:
                chk[i*j] = False
                j += 1
    res = [x for x in range(n+1) if chk[x]]
    return res
print(PrimeNumber(100))

 

결과)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

 

그런데 변수 m은 n의 제곱근이어서 반복을 n의 제곱근까지만 돌아줍니다. 

 

n의 제곱근까지만 돌아주어도 되는 이유를 설명해보겠습니다.

 

먼저 소수의 정의는 "1과 자기자신을 제외한 나머지 숫자로는 나눠지지 않는 숫자"입니다.

 

즉, 약수가 1과 자기자신만 있다는 겁니다.

 

n의 약수를 구해본다고 하겠습니다. n = 12일때 n은 자연수 a, b에 대해 n = a * b라고 표현할 수 있습니다.

 

12를 약수로 나누어 보면 [ 1, 2, 3, 4, 6, 12 ] 이렇게 나오고 약수는 모두 자연수입니다.

 

n의 약수는 m = sqrt(n)라고 쓸 수 있습니다. (sqrt는 square root의 약자이고 제곱근을 의미합니다.)

 

여기서 기억해야 할 2가지가 있습니다. 

 

1. 12의 square root는 2√3이 되고 √3은 1.7XXX..정도니 대략 3.4XXX..가 됩니다. 즉, 12의 약수의 중간값이(여기선 3) 12의 제곱근보다 작습니다.

 

2. 약수는 대칭성을 띄고 있습니다. 1*12, 2*6, 3*4 등 약수끼리의 곱은 n이 나옵니다.

 

다시 돌아와서 n = a*b이라고 했으므로 n = m*m이라고도 할 수 있습니다.

 

그렇다면 n = a*b = m*m 이됩니다. a와 b가 자연수가 되기 위해서는 3가지 중 하나에 속해야 합니다.

 

1) a = m and b = m

2) a < m and b > m

3) a > m and b < m

 

n의 약수가 되는 a, b는 반드시 m과 작거나 같아야 한다는 뜻입니다. min(a, b) <= m

 

그리고 m은 sqrt(n)입니다. 소수는 1과 자기자신 이외에 약수는 없어야 하므로 반복문으로 n % i == 0을 돌리는데 한번이라도 걸리면 그 i는 a이며 약수가 발견되었기 때문에 n은 소수가 아니게 됩니다.

 

2번 조건에 의해 약수는 대칭성을 띄고 있어 a가 걸린다면 b도 있다는 의미이므로 중간값보다 약간 큰 수인 n의 제곱근까지만 탐색을 해주어도 무방합니다.