소수의 판별

개요

소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않은 자연수이다. 예를 들어 7은 1과 7을 제외하고는 나누어 떨어지지 않기 때문에 소수이다. 이러한 소수를 구하기 위한 알고리즘은 크게 2가지가 있다.

개선된 소수 판별 알고리즘

코드를 작성하기 전에 소수의 특징에 대해서 먼저 살펴보자. 예시로 16이라는 수의 약수는 1 2 4 8 16 이 있다. 이때 모든 약수에 대하여, 가운데 약수를 기준으로 하여 대칭적으로 2개씩 앞뒤로 묶어서 곱하면 16을 만들 수 있다.

이러한 특징을 통해 소수인지 알고 싶은 수의 제곱근 까지만 나누어떨어지는 지 확인하면 된다. (위의 예시에서는 4)

개선된 소수 판별 알고리즘 소스코드

import math

def is_prime_number(x):
    #2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        #만약에 x가 해당 수로 나누어 떨어진다면
        if x % i == 0:
            return False #소수가 아님
    return True

print(is_prime_number(4)) #False
print(is_prime_number(7)) #True

• 시간 복잡도는 O(X^1/2)

에라토스테네스의 체

에라토스테네스의 체는 여러개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다. 이는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다 (i는 제거하지 않는다)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다

N = 26이 소수인지 판별하는 에라토스테네스의 체는 아래와 같다.

에라토스테네스의 체 소스 코드

import math

n = 1000 # 2부터 1000까지의 모든 수에 대하여 소수 판별
array = [True for _ in range(n + 1)]

#에라토스테네서의 체 알고리즘
for i in range(2, int(math.sqrt(n)) + 1):
    #i가 소수인 경우
    if array[i] == True:
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1

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

• 시간 복잡도는 O(NloglogN) 으로 선형 시간에 동작할 정도로 빠르다.
• 이 알고리즘은 다수의 소수를 찾아야 하는 문제에서 자주 활용된다. 하지만 메모리가 많이 필요하다는 단점이 있다. 알고리즘을 수행할 때 N의 크기만큼 리스트를 할당하기 때문이다.
• 따라서 10억이 소수인지 찾아야 하는 문제에서는 사용하기 힘들다.