Python 파이썬 - 소수 판별 알고리즘 (에라토스테네스의 체)

가끔 알고리즘 문제에 나오는 소수계산을 위해 정리하는 글이다.

소수란, 1과 자기 자신 이외에 약수를 가지지 않는 1보다 큰 자연수 이다.

 

1은 소수가 아니다

 

소수 판별 알고리즘은 대표적으로 두가지 방법으로 구현 할  수 있다.

 

 

일반적인 방법

 

우선, 반복문을 사용하는 것이다. 

이 방법은 1개의 숫자가 소수인지 아닌지 판별하는데 사용하면 좋다.
여러 숫자를 소수 판별해야하는 경우는 아래 있는 에라토스테네스의 체가 더 유용하다.

 

n이라는 숫자가 소수인지 확인하기 위해서는 2부터 n-1까지 나눠보면서 나머지가 0이 나오는 숫자가 한개도 없으면 n은 소수이다. 

 

하지만 n-1까지 나눠보지 않더고 √n 까지만 확인해봐도 된다. 

 

소스코드 

 

import sys, math

# 소수 판별 알고리즘 : 제곱근까지 구하기
def isPrime(x):
    if x == 1: # 1은 소수가 아님
        return False
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

 

 

 

에라토스테네스의 체

 

다른 방법으로는 에라토스테네스의 체가 있다. 위의 방법과 비슷하지만, 소수 판별을 해야하는 숫자가 많을 때 유리하다.

 

왜냐하면 리스트에 2부터 n까지에 대해 소수 여부를 저장하기 때문에 한번 계산해두고, 해당 숫자가 소수인지 확인하는 것은 O(1)이 걸리기 때문이다. 

 

단, 2부터 n까지의 소수 여부를 저장하는 배열이 필요하므로 그만큼 공간복잡도가 들어간다.

 

소스코드

 

import sys, math
target = 1000 # 구하려는 값의 범위
#에라토스테네스의 체
prime = [True]*(target) 
prime[1] = False # 1은 소수가 아님
m = int(math.sqrt(target))
for i in range(2, m+1):
    if prime[i] == True:
        for j in range(i+i, target, i):
            prime[j] = False