소수 알고리즘 파이썬 - sosu algolijeum paisseon

중학교 1학년 교과과정의 시작은 소수를 찾는 것부터 시작합니다. 에라토스네스의 체를 이용하여 소수를 판별하는 법을 배우면서 2, 3, 5, 7, 11, ...로 이어지는 소수의 수열을 배웁니다.

오늘은 소수의 정의를 이용해서 파이썬으로 소수를 구별하는 코드를 만들어 보려 합니다.

여러분도 잘 아시다시피, 소수의 정의는 '1과 자기 자신 외에 양의 약수가 없는 1보다 큰 자연수'입니다.

따라서, 자연수 중에서 1은 소수가 아닙니다. 

2부터 소수가 될 자격이 있는데, 6과 같은 수는 1, 2, 3, 6을 양의 약수로 갖기 때문에 소수가 아닙니다. 6을 예로 들어서 설명하면, 6을 2부터 자신보다 1이 작은 수들인 [2, 3, 4, 5]로 나누어 보면, 나머지는 [0, 0, 2, 1]이 됩니다. 결국, 자연수 6은 [1, 6] 이외에도 [2, 3]으로 나누어도 나머지가 0이 되기 때문에 소수가 아닙니다.  

이번에는 자연수 5를 예로 들어보겠습니다. 5를 2부터 자신보다 1이 작은 수인 [2, 3, 4]로 나누어 보면, 나머지는 [1, 2, 1]이 됩니다. 자연수 5는 [1, 5] 이외에는 나누어도 나머지가 0이 되지 않기 때문에 [2, 3, 4]를 양의 약수로 갖지 않습니다. 따라서, 소수가 분명합니다.  

파이썬으로 소수를 판별하는 코드를 작성해 보겠습니다. 

def prime_number(number):   # number를 입력 받아 소수인지 아닌지 구분하는 함수
     # number가 1이 아니면, (1은 소수가 아님)
    if number != 1:                 
        # 2, 3, 4, ..., (number - 1)까지의 인수에 대해서
        for f in range(2, number):  
            # number가 위의 인수 중의 하나로 나누어지면, (나머지가 0이면)
            if number % f == 0:     
                return False    # 소수가 아님
    else:                       # number가 1이라면, 
        return False            # 소수가 아님
    
    # number가 1이 아니면서, 2부터 (number - 1)까지의 수로 나눠지지 않으므로
    # 소수로 판별됨 (소수는 1과 자신만을 인수로 갖는 수)
    return True                 

   
num = input("Input a number: ")
if prime_number(int(num)):
    print("TRUE: The input number " + num + " is a prime number.")
else:
    print("FALSE: The input number " + num + " is NOT a prime number.")

파이썬 코드를 실행하고 number로 20과 17을 입력하면, 20은 소수가 아니고 17은 소수라고 판별합니다. 오류 없이 잘 작성된 것 같습니다. 

Input a number: 20
FALSE: The input number 20 is NOT a prime number.

Input a number: 17
TRUE: The input number 17 is a prime number.

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

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

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

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

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