소수 판별 알고리즘

• 하나의 수에 대해서 소수인지 아닌지 판별하는 알고리즘

기본적인 알고리즘

소스코드 (Python)

# 소수 판별 함수 (2 이상의 자연수에 대해)
def is_prime_number(x):
    # 2부터 (x-1)까지의 모든 수를 확인하며
    for i in range(2, x):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
        	# 소수가 아님
            return False
    # 소수임
    return True

성능 분석

• 시간 복잡도 : $O(N)$
  • 2부터 N-1까지 모든 자연수에 대해 연산 수행

개선된 알고리즘

약수의 성질

• 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭
  • ex. 16의 약수 = 1, 2, 4, 8, 16
• 따라서 특정한 자연수의 모든 약수를 찾을 때, 가운데 약수(=제곱근)까지만 확인하면 됨
  • ex. 2가 16의 약수라는 것은 8도 16의 약수라는 것을 의미

소스코드 (Python)

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(N^{1/2})$
  • 2부터 N의 제곱근까지의 모든 자연수에 대해 연산 수행

에라토스테네스의 체

• 고대 그리스 수학자 에라토스테네스가 발견한 소수 판별 알고리즘
• 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 하는 경우 사용 가능
• 다수의 자연수에 대해 소수 여부를 판별할 때 사용하는 대표적인 알고리즘

동작 과정

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

소스코드 (Python)

import math

# 처음엔 모든 수가 소수(True)인 것으로 초기화
array = [True for i in range(n + 1)]

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

성능 분석

• 시간 복잡도 : $O(NloglogN)$
• 수행 시간은 매우 빠르지만 N의 크기만큼 배열을 할당해야 하기 때문에 메모리가 많이 필요함