[내가 보려고 적는 파이썬] 소수 판별(에라토스테네스의 체)

소수 판별 알고리즘

소수란?

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

# 기본적인 소수 판별 방법(2부터 n-1까지 돌려보기)
def is_prime_number(x):
  # 2부터 (x - 1)까지의 모든 수를 확인
  for i in range(2, x):
  	# x가 해당 수로 나누어떨어지면
    if x % i == 0:
    	return False
  return True
  
print(is_prime_number(4)) # False

시간복잡도는 O(X)이므로 X의 크기가 크면 비효율적이다.
좀 더 효율적인 방법으로는 제곱근 까지만 확인을 하는 것이다.
예를 들자면, 16의 약수는 다음과 같다.

• [1, 2, 4, 8 16]

해당 수를 살펴보면 가운데 수를 기준으로 대칭적으로 곱을 통해 16을 만들 수 있다. 이를 통해, 소수의 절반에 해당하는 제곱근까지만 살펴보면 소수 판별이 가능하다는 것을 알 수 있다.

import math

# 제곱근까지만 보고 소수를 판별하는 함수
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x))+1):
    # x가 해당 수로 나누어 떨어진다면
    if x % i == 0:
        return False
    return True

개선된 알고리즘의 시간복잡도는 O(X^(1/2))라고 할 수 있다. 하지만, 여러 수에 대한 소수 판별에는 비효율적일 수 있다.
이러한 경우에는 에라토스테네스의 체라는 알고리즘을 활용한다.

에라토스테네스의 체

이는 범위에 대한 소수 판별에 유리하다. 하는 방법은 다음과 같다.

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

import math

# 소수 판별 함수(에라토스테네스의 체)
def is_prime_number(n):
    # 2부터 n까지의 모든 수에 대하여 소수 판별
    array = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)

    # 에라토스테네스의 체
    for i in range(2, int(math.sqrt(n)) + 1): #2부터 n의 제곱근까지의 모든 수를 확인하며
        if array[i] == True: # i가 소수인 경우(남은 수인 경우)
            # i를 제외한 i의 모든 배수를 지우기
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1

    return [ i for i in range(2, n+1) if array[i] ]

# N이 1,000,000 이내로 주어지는 경우 활용할 것 => 이론상 400만번 정도 연산이고 메모리도 충분함

print(is_prime_number(26))

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다. 하지만, N크기 만큼의 메모리를 저장하고 기억해야하므로 주의해야한다.

해당 문서는 이것이 코딩 테스트다. with 파이썬 - 나동빈 저의 책을 읽고 정리한 내용입니다.