[기타 알고리즘] 소수의 판별

 '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 의 appendix B의 순서에 해당하는 글들을 읽으며 정리하였다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

처음 등장하는 소수의 판별은 이미 과거에 정리한 글이 있기 때문에 그 글 또한 참고하며 정리하였다.

kom-story.tistory.com/3

 

소수(Prime Number)란 ?

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

소수 판별 함수

ver1 , 무식하게 소수 판별하기 (시간 복잡도 : O(n))

def is_prime_number(x) :
	for i in range(2,x) :
    	if x%i == 0:
        	return False
    return True
    
    
print(is_prime_number(4)) # False
print(is_prime_number(7)) # True

 

 

ver2. 머리쓰기 (시간 복잡도 :O(n^(1/2)))

x라는 수의 모든 약수에 대하여 가운데 약수를 기준으로, 대칭적으로 2개씩 앞뒤로 묶어서 곱하면 x를 만들이는 수 있다.

따라서 특정 자연수 x가 소수인지를 확인하기 위해 가운데 약수 까지만 나누어 떨어지는지 확인하면 된다. 이는 x의 제곱근 까지만 확인해도 된다는 의미이다.

import math

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

 

하지만 이 방법 또한 하나의 수에 대해서만 소수인지 아닌지 판별하는ㄴ 것이 아닌 전체 수의 범위 안에서 존재하는 모든 소수를 찾아야 할 때는 다른 방법이 더 효율적일 것이다.

 

에라토스테네스의 체

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

에라토스테네스 체의 알고리즘은 다음과 같다.

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

2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다).

4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

 

과거에 에라토스테네스의 체를 통해 어떠한 범위에서 소수를 찾는 문제는 다음과 같이 해결했었다.

def solution(n):
    num = set(range(2,n+1))
    for i in range(2,n+1) :
        if i in num :
            num -= set(range(2*i,n+1,i))
    return num

 

 

책에서 제시하는 1부터 N까지의 모든 소수를 출력하는 프로그램을 작성하자.

매 스텝마다 남은 수 중 아직 처리하지 않은 가장 작은 수 i를 찾을 때에는 위의 ver2에서 언급했듯이 N의 제곱근 (가운데 약수)까지만 증가시켜 확인하면 된다. 1이 소수인지 아닌지 판별해야할 수 있으므로 이를 주의하면서 코드를 짜면 다음과 같다.

import math

n = 1000 # 2부터 1000까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n+1)] # 처음에 모든 수가 소수(True) 인 것으로 초기화 (0,1 제외)

for i in range(2, int(math.sqrt(n))+1) : 
	if array[i] == True :
    	# i를 제외한 i의 모든 배수 지우기 작업 수행
    	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=' ')

 

이는 위에서 과거에 정리한 것과 합치면 더 효율적인 것 같아서 다음과 같이 만들어보았다.

import math

def solution(n):
    num = set(range(2,n+1))
    for i in range(2,n+1) :
        if i in num :
            num -= set(range(2*i,n+1,i))
    return list(num)
    
sosu = solution(1000)


for i in range(len(sosu)) :
    print(sosu[i],end=' ')

 

이는 O(NloglogN)으로 굉장히 빠르게 동작하기 때문에 다수의 소수를 찾는 경우 자주 사용된다. 하지만 이는 메모리가 많이 필요하다는 단점이 있다. 알고리즘 수행 시 N의 크기 만큼 리스트 혹은 집합을 할당해야 하기 때문이다. 

이는 N이 1,000,000 이내로 주어질 때 자주 사용된다.