파이썬 알고리즘 문제 - 소수 구하기

2보다 큰 자연수 중에 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수를 소수라고 말합니다.

보통 요즘 코딩테스트 문제에 단골주제로 많이 나오니 이번에 한번 알아보고자 합니다.

 

그리고 참고로 소수가 왜 중요한지 그리고 어디다가 사용하는지에 대해서는 다음 링크를 참고해주시고..

 

https://www.joongang.co.kr/article/22283770#home

실용성 없던 소수 연구, 암호학 만나 ‘몸값’ 크게 올라

 

https://www.hani.co.kr/arti/society/schooling/164651.html

기밀을 유지하고 싶을땐 ‘소수’를 이용하라

 

소수를 구하는 방법에는 보통 두가지 방법이 있습니다.

첫번째는 정말 소수 그자체를 구하기 위해 소인수분해하는 방법이 있고...

두번째는 "아라토스테네스의 체"라고 하는 고대 그리스 수학자가 고안한 방식이 있습니다. (고대 사람인대 저보다 낫네요;;)

 

첫번째 방식의 경우는 소수의 정의대로 구현하는 방식은 다음과 같습니다.

import time

n = 10000
start_time = time.time()
for i in range(2, n+1):
    result = True
    for j in range(2, i):
        if i % j == 0:
            result = False
    if result:
        print(i, end=" ")
end_time = time.time()

print("\n")
print("일반시간", end_time - start_time)

실행결과화면

소요시간이 대략 0.085초 걸렸네요.

 

그럼 두번째 방식인 "아라토스테네스의 체"방식을 알아보기 전에 어떤 알고리즘으로 동작되는지 아래 그림을 참고해보시면 좋을꺼 같습니다.

아라토스테네스의 체 방식

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

이 방식을 코드로 구현하면 다음과 같습니다.

import time

n = 1000

start_time = time.time()
a = [False,False] + [True]*(n-1)
result=[]

for i in range(2, n+1):
    if a[i]:
        result.append(i)
        for s in range(2*i, n+1, i):
            a[s] = False
print(result)
end_time = time.time()

print("\n")
print("에리토스테네스의 체 시간", end_time - start_time)

실행된 소요시간은 0.00098 초 걸렸네요.

 

역시 일반적인 방법보다는 알고리즘을 사용해서 구현한 방식이 훨씬 빠르다는 것을 알 수 있습니다.

이러한 차이는 숫자가 늘어날수록(연산할게 많아질 수록) 그 진가가 발휘됩니다.

 

그러니 열씸히 공부해야겠지요;;;;;