소수판별 알고리즘

[자연수 n이 소수인지 판별하는 알고리즘]

소수의 정의는 2 이상의 자연 수 중 1과 자신만을 약수로 가지는 수이다.

따라서 자연수 n이 소수인지 확인하기 위해서는 n을 2부터 n - 1까지의 수로 나눠서 떨어지는 경우가 있는지를 확인하면 된다. 이렇게 할 경우 알고리즘의 시간복잡도가 O(n²)이 된다.

자연수의 약수에 대한 규칙을 살펴보면 연산 횟수를 줄일 수 있음을알 수 있다. 16의 약수를 오름차순으로 정리해보면 다음과 같다.

16의 약수 = {1, 2, 4, 8, 16}

이 약수들을 곱연산 한 결과가 16이 되는 경우는 아래와 같다.

1 * 16 = 16

2 * 8 = 16

4 * 4 = 16

8 * 2 = 16

16 * 1 = 16

 

1 * 16 과 16 * 1 그리고 2 * 8과 8 * 2 은 순서만 뒤바뀐 채 동일한 수들이 합성된 것이므로 각각 둘 중 하나만 확인하면 된다. 즉 자연수 n이 소수인지 판별하기 위해서는 n의 제곱근까지만 확인하면 된다는 것이다.

 

n = 8일 때의 예시를 추가로 보도록 하자.

8의 약수 = {1, 2, 4, 8}

연산결과가 8이 되는 약수들의 곱연산 경우는 아래와 같다.

1 * 8 = 8

2 * 4 = 8

4 * 2 = 8

8 * 1 = 8

8의 제곱근인 √8 ≒ 2.82842 이므로 2까지만 확인하면 소수 여부를 확인할 수 있다.

 

위 설명이 이해가 안된다면...

8의 제곱근인 √8 * √8 = 8이 되며 √8은 2.8284... 이므로

          2.8284... * 2.82842... = 8  이며, 이것을 (A) * (B) = 8 형태라고 보자.

변수(A)를  1.0부터 시작하여 0.1씩 증가시켜가며 (A) * (B) = 8 를 만족하는 연산들을 확인해보자.

 

1.0 * 8.0 = 8.0

1.1 * 7.2727272727272725... = 8.0

1.2 * 6.666666666666667... = 8.0

1.3 * 6.153846153846153... = 8.0

(중략)

2.6 * 3.0769230769230766... = 8.0

2.7 * 2.962962962962963... = 8.0

2.8 * 2.857142857142857... = 8.0

(중략)

2.8284271247461903... * 2.8284271247461903... = √8  * √8  = 8.0 ⬅︎  8의 제곱근

(중략)

2.857142857142857... * 2.8  = 8.0

2.962962962962963... * 2.7 = 8.0

3.0769230769230766... * 2.6 = 8.0

(중략)

6.153846153846153... * 1.3 = 8.0

6.666666666666667... * 1.2 = 8.0

7.2727272727272725... * 1.1 = 8.0

 8.0 * 1.0 = 8.0

 

좀 길게 나열했지만, (A), (B)가 각각 √8이 될 때를 기준으로   (A)와 (B)가 서로 반비례 하여 증감 됨을 확인할 수 있다.

 

위에 나열된 계산 결과 가운데 자연수만 추려낸 것이 위에서 살펴본 8의 약수들의 곱연산들이다. 다시 한번 살펴보자.

1 * 8 = 8

2 * 4 = 8

4 * 2 = 8

8 * 1 = 8

 

2 * 4 이나 4 * 2 모두 8을 만들기 위해 2와 4를 사용한 것이므로 동일한 소수판별 과정이라 볼 수 있다.

따라서  특정 수 N까지의 소수를 판별에 사용할 모든 약수들의 집합 D = {x ∣ 2 ≤ x ≤ √N인 모든 자연수}가 되므로 2 ~ N까지의 모든 자연수로 나눠 떨어지는지 확인하는 것보다 시간을 많이 절약할 수 있다.

 

python 코드로 옮겨보면 다음과 같다.

def confirm_prime_number(num):
    if num == 1:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

---

[자연수 n 이하의 소수 목록을 구하는 알고리즘 - 에라토스테네스의 체]

1. 2부터 n까지의 모든 자연수를 나열한다.

2. 소수판별이 완료되지 않은 수 가운데 최소인 수를 min_num이라 하자. 이 min_num은 소수이다.

3. 모든 수 가운데 min_num을 초과하는 min_num의 배수에 해당하는 수를 모두 제거한다.

4. 소수판별이 완료되지 않은 수가 없을 때까지 2, 3번 과정을 반복한다.

n = 1000
# 1 ~ 1000 모든 수가 소수라고 가정
prime_numbers = [True for i in range(n + 1)]
prime_numbers[1] = False
for i in range(2, int(n ** 0.5) + 1):  # 2 ~ n의 제곱근 까지 확인한다.
    if prime_numbers[i]:
        j = 2
        while i * j <= n:
            prime_numbers[i * j] = False
            j += 1

# 모든 소수 출력
for i in range(2, n + 1):
    if prime_numbers[i]:
        print(i, end=' ')