[Python 3.x] 파이썬 소수 구하기

오늘은 파이썬으로 소수 구하는 방법을 구현 할 것입니다.

소수란

자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.
여기서 소수를 구하는 코드를 구현하는 것은 크게 2가지가 있다.
한 가지는 에라토스테네스의 체가 있고, 다른 방법으론 2이상의 숫자로 1씩 더해가면서 숫자를 나누는 방법이 있다.

에리토스테네스의 체란

찾고자 하는 자연수를 배열로 나열하여 그 수중에 소수의 배수들을 전부 지워 나가게 된다면 남은 수가 소수가 된다.

https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif

코드 구현

에리토스테네스의 정리 없이 구현한 코드

n=1000
for i in range(n+1):
  result=True
  if(i<2):
    result = False
  for j in range(2,i):
    if(i%j==0):
      result = False
  if result:
      print(i, end=" ")

코드 결과

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997
0.065794초 걸렸습니다.

에리토스테네스의 체로 구현한 코드

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

코드 결과

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
0.000580초 걸렸습니다.

위의 알고리즘의 표본 개수가 1000개 밖에 되지 않는데도 불구하고 속도의 차이가 10배 이상이 나는걸로 보인다.

표본 개수를 10000으로 늘려본다면 얼마나 차이가 나는걸까?
6.021144초 걸렸습니다.
0.004945초 걸렸습니다.

둘의 시간차이가 표본의 수가 늘어날수록 많은 차이가 벌어집니다.
둘의 시간복잡도는

O(√n)
O(n (log n) (log log n)) 

의 차이가 납니다.
이거 외에도 소스 코드에서 함수처리 호출 처리 등에 따라서 1000개의 표본에서 위의 알고리즘이 0.06초가 걸리는 것을 0.6초가 되게 구현할수 도 있습니다.
서버를 구축 하실 때에는 사소한 알고리즘의 차이가 큰 수준을 바꾸게 되니 항상 코드를 짜실때 시간 복잡도를 염두를 하시고 개발하시면 좋을것 같습니다.

자료가 유용하셨다면 구독과 아래의 하트 눌러주세요.