소수 판별 알고리즘

다양한 구현 방법

시간복잡도 O(N)

• N이 소수인지 판별하는 가장 쉬운 방법
• 2부터 N-1까지의 수로 나누어 떨어지는지 확인, 나누어 떨어진다면 소수가 아니라고 판단함
• 비교적 시간이 오래 걸리는 알고리즘

def isPrime(N):
    if N < 2: 
    	return False
    for i in range(2, N):
    	if N%i == 0:
        	return False
    return True

시간복잡도 O(N), T(N) = N/2

• N이 1과 자기 자신을 제외한 약수를 가지고 있다고 할 때, 해당 약수들은 2, 3, 4, ..., N/4, N/3, N/2 중에 존재함
• N의 약수 중 최대 수는 (N 제외하고) N/2가 됨
• 따라서 2~N-1 모두 검사할 필요 없이, 2~N/2 까지의 수만 검사하면 됨

def isPrime(N):
    if N < 2: 
    	return False
    for i in range(2, N//2+1):
    	if N%i == 0: 
        	return False
    return True

시간복잡도 O(√N)

• N = a x b (a ≤ b) 라 할 때, a = 1, 2, 3, ..., √N 이면 자동적으로 b = √N, ..., N/3, N/2, N이 됨
• 이때 a가 될 수 있는 수들로만 나누어 떨어지는지 확인하면, 나머지 약수들은 자동적으로 확인 가능함

import math

def isPrime(N):
    if N < 2: 
    	return False
    for i in range(2, int(math.sqrt(N))+1): 
    	if N%i == 0:
        	return False
    return True

※ math 모듈 사용하지 않고 n의 제곱근 구하기

• n**(1/2)
• n**(0.5)

에라토스테네스의 체

• N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘

동작과정

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

시간복잡도 O(NloglogN)

• 사실상 선형 시간에 가까울 정도로 매우 빠름

성능 분석

• 다수의 소수를 찾아야하는 문제에서 효과적임
• 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요함

Python 코드

import math

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

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

# 모든 소수 출력
for i in range(2, n + 1):
    if prime[i]:
        print(i, end=' ')

[출처]
https://maramarathon.tistory.com/39