[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

 에라토스 테네스의 체를 통해서 소수를 판별하는 알고리즘을 알아보겠습니다.

 

[ Contents ]

 

 

1. 소수

소수(Prime): 약수가 1과 자기 자신밖에 없는 수

 '소수'는 1과 자기 자신으로만 나누어 떨어지는 자연수입니다. 반대로 1과 자기 자신 외에 다른 약수가 있으면 '합성수'라고 합니다.

 '소수 판별'은 특별한 공식이 없으며, 정의대로 1과 자기자신 사이의 수 중 약수가 있는지 검증해야 합니다. 숫자가 클수록 검증해야 하는 숫자들이 많아지며, 계산복잡도도 높아집니다. 따라서 RSA와 같은 각종 보안 알고리즘에 응용되며, 소수 판별 알고리즘의 중요성도 커지고 있습니다.

 만약 소수를 빠르게 찾아낼 수 있는 공식을 찾아낸다면, 블록체인을 비롯해서 사회 전반의 보안 알고리즘을 뚫어낼 수 있습니다. (그럴리 없겠지만...)

 

 

 

2. 소수 판별

n의 소수 판별: 2부터 제곱근 n까지 약수 있는지 판별

 자연수 n의 최대 약수는 루트 n 이하입니다. 생각해보면 굳이 2부터 n-1까지 약수인지 검증할 필요가 없습니다. 23의 약수가 15, 22일리는 없겠죠. 제일 작은 자연수인 2를 곱해도 23을 넘어가니까요.

 이런 논리로 최대 약수를 계산하면 제곱근 n이 나옵니다.

 

n이 소수인지 알아보기 위해, n이 합성수라는 가정을 하고 검증합니다.
합성수라면, n은 두 자연수의 곱으로 나타낼 수 있습니다.

n = A * B (단, A >= B)
A * A >= A * B
A^2 >= N
A >= 루트 n

 따라서 A의 최소값이자 B의 최댓값은 루트 n이 됩니다. ( B <= 루트 n <= A)

 즉, 루트 n까지만 약수 검증을 하면 B가 약수인지 확인할 수 있습니다.

 

 

 

3. 에라토스 테네스의 체

자연수 n까지의 소수 판별 과정
1) 2부터 n까지 모두 소수라고 가정합니다. (에라토스 테네스의 체)
2) 2부터 제곱근 n까지 소수인지 탐색하고, 소수이면 해당 배수를 소수에서 제외합니다.
3) 자기 차례가 되었는데도 제외되지 않았으면 그 수는 소수입니다.

 에네토스 테네스의 체는 '소수 판별'을 조금 더 쉽게 하는 방법입니다. 우선 모두 소수라고 가정하고, 그 소수의 배수를 모두 제외시키는 방법으로 진행합니다.

 

 

 맨 처음 시작하는 2와 3은 소수이며, 4는 2의 배수이기 때문에 제외됩니다. 5는 제외되지 않았으니 소수이며, 5의 배수들이 지워집니다. 이런 과정을 거치면 자연스럽게 해당 수의 차례가 되었을 때, 소수 검증이 완료됩니다. 

(빨간색: 2의 배수, 파란색: 3의 배수, 주황색: 5의 배수)

 

 

 

3. 코드

n = 100  # 1~100까지 소수 판별

# 에라토스 테네스의 체
primeList = [True] * n

# 소수 판별 알고리즘
def isPrime(n):
    if n == 1:  # 1은 소수가 아님
        return False

    for i in range(2, int(n ** 0.5) + 1):
        if primeList[i] == True: #i가 소수라면
            for j in range(2 * i, n, i):  # 2i부터 n까지 i의 배수들은 False
                primeList[j] = False

# 소수 출력
isPrime(n)
for i in range(2, n):
    if primeList[i]:
        print(i, end=" ")