소수 구하기의 여러가지 방법과 시간복잡도 비교

관련문제

• 백준 1978 소수 찾기
• 백준 9020 골드바흐의 추측

메모이제이션

• 메모이제이션 : 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
• 소수를 한 번만 찾는 경우는 메모이제이션이 필요 없겠지만 한 번 이상 찾으면 기존 결과를 저장해놓고 다시 찾는 것이 더 빠르다.
• 대신 공간 복잡도가 증가한다. 최대 N+1 ;n은 소수를 검사할 범위의 크기

범위랑 같은 크기의 배열에 인덱스로 표시하기

방법1.default를 False로 두고 찾기

N = 101
p = [False]*N
for i in range(2,N):
    for x in range(2,int(i**(1/2))+1):
        if(p[x]==False): continue  
        if(i%x==0) : 
            p[i] = False
            break
    else:
        p[i] = True

• 시간복잡도 O(N√N)

방법2.default를 True 로 두고 지우기(에라토스테네스의 체)

N=101 #범위보다 1 크게
p=[False,False]+[True]*(N-2) #0,1은 기본 처리
for i in range(2,N):
    if(p[i]==True):
        for x in range(i*2,N,i):
            p[x]=False
print(p)

• 시간복잡도 O(N log log N) : N/2 + N/3 + N/4 + … N/N

방법3.Prime 배열에 숫자를 직접 관리하기

N = 101
prime = [2,3]+[None]*(101//2)
ptr = 2
for n in range(5,N+1,2):
    i=0
    while prime[i]*prime[i] <=n:
        if(n%prime[i]==0): break
        i+=1
    else:
        prime[ptr]=n
        ptr+=1
print(prime)

• 공간복잡도는 범위와 같은 크기배열보다 줄어든다. N/2
• 시간복잡도 O(N√N) (최악의 경우)
  • default를 False도 O(N√N) 소수로 나누기 위해 소수를 탐색하는 if(p[x]==False) 부분에서 소수가 아닌 부분도 확인한다.
  • 반면 방법[3]은 이미 확인된 소수를 모아놓은 배열을 이용하기 때문에 기존에 찾은 소수들을 검사하는 시간 복잡도는 O(n/log n) 이다. 하지만 O(√N) 으로 근사하는 것이 더 정확하다고 한다. (Prime number theorem)
  • 어쨌든 O(n/log n) 이 O(√N) 보다 크다.

두 함수의 비교

어떤 방법을 쓸 것인가?

• 시간복잡도 면에서 에라토스테네스의 체가 가장 빠르고, 공간복잡도도 Big-O 로 따지면 모두 O(N)으로 같으므로 에라토스테네스의 체가 가장 좋아보인다.
• 에라토스테네스의 체의 코드가 가장 간결하기도 하다.
• 빠르기는 에라토스테네스의 체 > Prime 배열에 숫자로 관리하기 > default를 False로 두고 하나씩 찾기

추가 스킬

• 위의 백준 문제들처럼 특정 범위가 주어지고 , 여러개의 소수를 판별하는 문제는 메모이제이션으로 푸는 것이 더 빠를 수 있지만, 메모이제이션의 범위를 너무 크게 잡으면 불필요한 계산을 할 수도 있다.
• 이를 방지하기 위해서 입력을 모두 받고 가장 큰 숫자를 기준으로 에라토스테네스의 체 메모이제이션을 한 후 나머지는 메모에 접근하기만 하면 더 효율적이겠다.

import sys
input = sys.stdin.readline
input()
N=list(map(int,input().split()))
maxN=max(N)+1  #  최대 수 구하기
p = [0,0]+[1]*(maxN-2)
for i in range(2,maxN):
    if(p[i]==1):
        for x in range(i*2,maxN,i):
            p[x]=0
cnt = 0
for i in N:
    if(p[i]==1): cnt+=1
print(cnt)

import sys
sys = sys.stdin.readline

T=int(input())
N=[int(input()) for _ in range(T)]
maxN = max(N)+1  ## 최대 수 구하기
p = [False,False] + [True] * maxN
for i in range(2,maxN):
    if(p[i]):
        for x in range(i*2,maxN,i):
            p[x]=False

for n in N:
    for i in range(n//2,n):
        if(p[i] and p[n-i]):
            print(n-i,i)
            break

• 소수를 구하는 알고리즘 상 어차피 순차적으로 작은 소수들이 모두 구해지므로 동적 계획까지는 쓰지 않아도 된다.