[Python] N까지의 소수 구하기 최적화 방법

---

Python으로 N까지의 소수 구하기 최적화

N까지의 소수를 모두 구하는 문제는 알고리즘 풀이 사이트 빈출 유형일 뿐만 아니라, 기업체에서 가볍게 보는 라이브 코딩이나 손코딩 문제로 매우 자주 출제된다. 

그 이유는, 난이도 자체는 쉽지만 최적화 할 수 있는 여지가 굉장히 많기 때문이다.

대표적인 손코딩/라이브코딩 시나리오는 아래와 같다.

1. for문으로 한번 짜보실래요?

2. 지금 코드의 시간복잡도 설명해보실래요?

3. for문의 연산 수를 줄일 수 있는 방법이 있을까요?

4. 이 보다도 더 줄일 수 있는 방법이 있을까요?

시나리오를 따라서 한번 문제를 풀어보자!

 

 

Req1) 단순 반복문으로 짜보실래요?

---

def GetPrimeNoOpt(n):
    res = []
    for i in range(2, n+1):
        is_prime = True
        for j in range(2, i):
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            res.append(i)
    return res

 

• 2부터 n-1까지의 숫자들 중 약수가 존재하면 소수가 아니다.
  
  
• 만약 끝까지 약수가 없었으면 소수 목록에 추가
  
  
• 시간복잡도 N^2

 

 

Req2) For문 연산 수를 줄여보실래요?

---

def GetPrimeSqrt(n):
    res = []
    for i in range(2, n+1):
        is_prime = True
        for j in range(2, int(math.sqrt(i))+1):
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            res.append(i)
    return res

 

• 약수는 항상 대칭성의 원리를 만족함
  
  
• 16의 약수 1,2,4,8,16은 중앙값 4를 중심으로 했을 때,  2로 곱하고, 나누고를 통해서 만들어 낼 수 있는 숫자임
  
  
• 즉, 숫자 N의 소수 여부를 판별하기 위해서는, 굳이 N-1까지의 약수를 모두 체크할 필요 없이, N의 제곱근까지만 검사했을 때 약수가 없으면, 그냥 약수가 없다는 것을 의미함
  
  
• 이를 활용하면 시간복잡도를 nlogn으로 줄일 수 있음
  

 

Req3) 그럼 실행시간을 여기서 더 줄일 수 있는 방법이 있을까요?

---

def GetPrimeEratosthenes(n):
    chk = [True]*(n+1)
    res = []
    chk[0], chk[1] = False, False
    for i in range(2, int(math.sqrt(n))+1):
        if chk[i]:
            res.append(i)
            j = 2
            while i*j <= n:
                chk[i*j] = False
                j += 1
    res = [x for x in range(n+1) if chk[x]]
    return res

 

• 취준 중에 알고리즘 문제 사이트에서 문제를 풀었다면 한번쯤 만나봤을, "에라토스테네스의 체"를 활용할 수 있다.
  
  
• 그리고 에라토스테네스의 체를 사용할 때에도, 위의 대칭성의 원리를 활용하면 더 연산량을 줄일 수 있다.
  
  
• 해당 방식은 n이 클 때 유리한 방법으로, 불필요한 반복 연산을 줄여준다.

 

 

100,000까지의 소수 구하기 실행 시간 비교

---

실제로 최적화가 효과가 있었는지, 실험을 진행해보자.

1부터 100,000까지의 소수를 위의 세가지 방식으로 구해보고 걸린 시간을 측정해봤다.

 

# get prime numbers in range(1, N)
# GetPrimeNoOpt - No Optimization
# GetPrimeSqrt - Sqrt Optimization
# GetPrimeEratosthenes - Sieve of Eratosthenes
import math, time

def GetPrimeNoOpt(n):
    res = []
    for i in range(2, n+1):
        is_prime = True
        for j in range(2, i):
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            res.append(i)
    return res

def GetPrimeSqrt(n):
    res = []
    for i in range(2, n+1):
        is_prime = True
        for j in range(2, int(math.sqrt(i))+1):
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            res.append(i)
    return res

def GetPrimeEratosthenes(n):
    chk = [True]*(n+1)
    res = []
    chk[0], chk[1] = False, False
    for i in range(2, int(math.sqrt(n))+1):
        if chk[i]:
            res.append(i)
            j = 2
            while i*j <= n:
                chk[i*j] = False
                j += 1
    res = [x for x in range(n+1) if chk[x]]
    return res

start = time.time()
GetPrimeNoOpt(100000)
print("GetPrimeNoOpt")
print(f"{(time.time() - start)*1000}ms")
start = time.time()
GetPrimeSqrt(100000)
print("GetPrimeSqrt")
print(f"{(time.time() - start)*1000}ms")
start = time.time()
GetPrimeEratosthenes(100000)
print("GetPrimeEratosthenes")
print(f"{(time.time() - start)*1000}ms")

 

결과

GetPrimeNoOpt
11862.13207244873ms 
# 약 11.86초

GetPrimeSqrt
73.03857803344727ms
# 73 ms

GetPrimeEratosthenes
13.015270233154297ms
# 13 ms

 

• 사소한 테크닉의 적용이 어마어마한 시간 차이를 발생시킨다는 것을 확인할 수 있다.