소수 판별

소수란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어 떨어지지 않는 자연수를 의미한다.

소수를 판별하는 가장 쉬운 방법은 판별해야 하는 수 X가 주어졌을 때, X를 2부터 X-1까지 나누어 보면 된다.

이를 이용한 코드는 아래와 같다.

def is_prime(x):
	for i in range(2,x):
    	if x % i == 0:
        	return False
        else:
    return True
    
print(is_prime(6))
print(is_prime(5))

---
False
True

위와 같은 코드는 정상적으로 동작하지만, 모든 경우의 수를 확인하기 때문에 O(x) 만큼의 시간 복잡도를 갖는다.

이를 개선하기 위한 방법으로, 2부터 X의 제곱근 까지 존재하는 자연수가 X를 나누어 떨어지게 할 수 있는지 확인할 수 있다.

이는 자연수가 자신의 약수를 기준으로 하여 대칭적으로 존재함을 이용한다.

예를 들어 8의 약수는 1 2 4 8 인데,

• 1x8 = 8
• 2x4 = 8
• 4x2 = 8
• 8x1 = 8

이기 때문에, 2까지만 수행하면 소수인지 판별할 수 있다.

코드는 아래와 같다.

import math

def is_prime(x):
	for i in range(2, int(math.sqrt(x)) + 1):
    	if x % i == 0:
        	return False
    return True
    
print(is_prime(5))
print(is_prime(6))

---
True
False

위와 같이 코드를 작성할 경우, 시간복잡도가 O(X^0.5)로 줄어든다.

---

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

알고리즘의 과정은 다음과 같다.

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

예를 들어, N이 26인 경우

[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26] 에서 에라토스테네스의 체를 수행하면

[2, 3, 5, 7, 11, 13, 17, 19, 23] 가 도출된다.

위 과정 역시, N의 제곱근 까지만 수행하면 된다. (약수가 대칭임을 이용)

아래 코드는 N이 1000 일때의 에라토스테네스의 체를 나타낸다.

import math

n = 1000
array = [True for i in range(n+1)]

for i in range(2, int(math.sqrt(n))+1):
	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=" ")
        
---
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...

에라토스테네스의 체 알고리즘은 O(NloglogN) 수준의 시간 복잡도로, 사실상 선형 시간에 동작한다.

하지만 초기 array를 할당할 때 메모리 공간을 많이 차지하기 때문에, N이 10억 이상인 경우에서는 사용이 힘들다.