[파이썬과 알고리즘] 소수 판별 알고리즘(에라토스테네스의 체, 직접 나누기)

소수 찾기

백준에 있는 문제들을 해결하면서 소수와 관련된 많은 문제들을 접했다.
소수를 판별하는 방법으로 잘 알려진 에라토스테네스의 체와 직접 나누어서 판별하는 방법을 이번에 간단히 알아보고 구현해 보았다.

에라토스테네스의 체

• 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾을 때, 가장 간단하고 빠른 방법이다.
• 가령, n부터 2n 내의 소수를 찾기 위해 2부터 2n까지 배수를 지워나가고 최종적으로 남는 수는 소수로 판정하는 방법이다.
• 체처럼 걸러낸다 하여 에라토스테네스의 체라는 이름이 붙은 듯하다.

1. 2의 배수 삭제

출처:나무위키

2. 3의 배수 삭제

출처:나무위키

3. 5의 배수 삭제(4의 배수는 2의 배수이므로 삭제되었음)

출처:나무위키

코드

1부터 N까지 수 중에서 소수를 출력하는 코드를 짜보았다.

def  get_primenumber(n):
    number=[i for i in range(2,n+1)]    # 1부터 n까지 리스트를 만듦
    num_dic=dict.fromkeys(number,1)     # 값이 1인 딕셔너리 생성
    prime_number=[]                     # 소수가 들어갈 리스트 생성
    start=2                             # 1은 소수가 아니므로 제외

    while start<=n:                     # 2부터 n까지 반복 
        if num_dic[start]==1:           # 소수라면 
            prime_number.append(start)  # 리스트에 추가
            for i in range(start*2,n+1,start):  # 배수의 값을 모두 0으로 바꿈
                num_dic[i]=0
        start+=1
    return prime_number


m,n=map(int,input('n을 입력:').split())
print(get_primenumber(m,n))

직접 나누기

이 방법은 어떤 수가 주어졌을 때, 소수인지 판별하는 방법이다.
소수는 1과 자기 자신을 약수로 가진다는 성질을 이용하여 이외의 수로 나누어서 나누어 떨어지는지 확인하는 방법이다.
이때, 약수는 항상 쌍으로 존재하기 때문에 1부터 N까지 나누는 것이 아니라 $\sqrt N$까지만 나누면 된다.

 

코드

def isprime(num):
    start=2

    while start<=num**0.5:    # 루트 N까지만 반복
        if num%start==0:     # 나누어 떨어지면
          return False       # 소수가 아니므로 False를 반환
        start+=1
    return True              # 소수는 True를 반환

 

 

이 두 알고리즘으로 백준 약수, 소수, 배수 단계의 모든 문제를 해결할 수 있었다.
하지만 글을 작성하며 자료조사를 한 결과 다른 소수 판별법이 있음을 알게 되었다.
다만, 다른 알고리즘들은 확률적으로 소수인지 판별한다거나(페르마 소수판별법 등) 검사할 수 있는 수의 범위가 제한적이었다.(윌슨의 정리)

위 두 방법들은 확실하게 소수인지 판별할 수 있지만, 비효율적이라는 단점이 존재한다.

상황에 맞게 적절한 알고리즘을 사용하는 것이 좋을 것이다.

출처

에라토스테네스의 체 나무위키
소수 판별법 위키백과