소수 알고리즘

소수(prime number)란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다.

 

코딩테스트에서 숫자가 소수인지 판별하는 경우가 간혹 생기므로 정리해본다.

먼저 무식하게 판별하는 방법이 있다.

def is_prime_number(x):
    for i in range(2,x):
        #x가 해당 수로 나누어 떨어진다면
        if x%i == 0:
            return False
    return True

이 방법의 시간복잡도는 O(X)이다.

 

이보다 더 빠른 방법은 자연수의 약수(Divisor)가 가지는 특징을 이용해서 구하는 방법이다.

예를 들어 10의 약수를 보자

 

1,2,5,10

1x10 = 10

2x5 = 10

 

가운데를 기준으로 대칭적인 형태를 이루는 것을 알 수 있다.

그렇기 때문에 우리는 자연수 x의 소수여부를 판별할 때 x의 제곱근까지만 확인해보면 된다.

import math

def is_prime_number2(x):
    #2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2,int(math.sqrt(x)+1)):
        if x % i == 0:
            return False
    return True

시간복잡도는 O($x^{\frac{1}{2}}$)이다. 시간복잡도가 매우 많이 개선되었음을 알 수 있다.

그러나 판별해야하는 수가 한 개가 아니라면 어떡할까? 이 알고리즘을 써서 하나씩 검사하는 것은 다소 비효율적이다.

 

에라토스테네스의 체

특정범위가 정해지고 그 범위 내 소수를 찾아야 한다면, 에라토스테네스의 방법보다 좋은 방법은 없다.

알고리즘은 다음과 같다.

 

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

 

초기상태 1은 소수가 아니므로 제거

	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

2를 제외한 2의 배수 제거

	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

3의배수, 4의배수.... 더이상 처리 할 수 없을 때까지 과정 반복

	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

소수가 2,3,5,7,11,13,17,19,23임을 구할 수 있음

 

import math

n = 25 #2부터 25까지 소수 판별
array = [True for i in range(n+1)]

for i in range(2,int(math.sqrt(n))+1):
    if array[i] == True: #i가 소수인 경우
        #i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i * j <= n:
            array[i*j] = False
            j += 1

에라토스테네스의 체 알고리즘의 시각복잡도는 $O(N\log logN) $이다.

에라토네스 체 알고리즘은 매우 빠르게 동작하지만 그만큼 메모리가 많이 필요하다는 단점이 있다. 

그래서 N이 1,000,000이내로 주어지는 경우가 많다.

 

참고서적 한빛미디어 이것이 코딩테스트다 with 파이썬