본문 바로가기

카테고리 없음

Python 소수(Prime) 찾기 알고리즘, 에라토스테네스의체

728x90

개요

알고리즘 문제를 풀다보면 혹은 수학문제를 풀다 보면 '소수'에 대한 언급이 자주 나옵니다. 소수(Prime, )는 1과 자기 자신을 제외하고는 나누어 떨어지는 수가 없는 수 입니다. 예로 2, 3, 5, 7, 11 ... 등이 소수 입니다. 

def sieve(N):  
   ns = list(range(2, N + 1))
   check = [True] * len(ns)

   i = 0
   while ns[i] * ns[i] <= N:
       if check[i]:
           for j in range(ns[i] + i, len(ns), ns[i]):
               check[j] = False
       i += 1

   primes = []
   for i in range(len(check)):
       if check[i]:
           primes.append(ns[i])
   return primes

N = 1000000 # 100만까지 소수
res = sieve(N)
print(len(res), res)

 

 

에라토스테네스의 체 유투브 동영상 강의

https://www.youtube.com/watch?v=rG7KFGZ7SV8 

 

 

왜 자꾸 소수(Prime)를 구하라는 문제를 내는 것일까요?

소수의 소는 '작을 소'가 아닌 '본디 소'입니다. 숫자를 이루는 수입니다. 2 이상의 모든 자연수는 소수의 곱으로 표현할 수 있기 때문입니다. 홀수는 자연수 + 1을 해주면 모든 자연수가 표현 가능 합니다. 10은 소수2와 소수5를 곱하면 됩니다. 27은 23 * 2 + 1을 하면 만들어낼 수 있습니다. 이런 이유로 소수의 성질에 대해 공부할 필요가 있다는 것입니다.

 

소수는 아주 오래전에 발견 되었습니다. 이집트 피라미드는 돌을 몇개나 깎아야 할까요? 이런 문제를 계산 한다고 했을 때 소수의 성질을 이용해 계산을 해볼 수 있겠지요?

 

프로그램으로 예를들면 100을 만드는 기능을 설계를 해본다면 2가 몇개가 필요할까? 100을 2와 3으로 만들 수 있을까? 이런 생각들을 해보게 됩니다.

 

100을 5로도 만들 수 있을까? 100을 7만으로도 만들 수 있을까? 7만으로는 못만들면 7과 1로는 만들 수 있을까? 이런 생각들이지요.

 

이집트 기자의 피라미드의 높이는 약 147미터입니다. 147미터의 피라미드를 만들려면 7미터의 돌을 몇개를 깎아야 할까? 7미터의 돌만으로는 될까? 이런 생각들을 피라미드의 설계 프로젝트 팀은 했을 것입니다.

 

피라미드를 만드는 것이나 프로그램을 만드는 것이나 소수가 필요할 때가 있습니다. 그러면 소수를 찾는 알고리즘을 한번 만들어보겠습니다.

 

단순하게 모두 찾기

def is_prime(n):
    for diviser in range(2, n):# 1 2 3 4 5
        if n % diviser == 0:
            return False
    return True

for i in range(2, 20):
    print(i, is_prime(i))

is_prime(n)함수를 만들어서 숫자 n이 소수인지 알아보는 알고리즘 입니다. 11은 소수입니다 is_prime(11)의 결과는 입력받은 n을 2부터 10까지 나눈 나머지가 0이 아닌 값이 나오는 동안 계속 나누어보는 식입니다.

 

위 로직으로 100,000이하의 소수를 찾으려면 시간이 아주 많이 걸립니다. 결과는 99991입니다. 100만 이하는 999983입니다.

 

하지만 알고리즘 문제는 100만 이상 1000만 1억까지도 제한을 합니다.

 

조금 더 빨리 하는 방법은 2부터 n까지 확인하는게 아니라 n/2까지만 확인하는 방법입니다. 어떤 수가 소수가 아니라고 하면 a의 최소값은 2이고 b의 최대값은 n/2입니다.

 

하지만 이렇게 해도 속도가 그렇게 빨라지지는 않습니다. 소수(Prime)에 관련된 알고리즘의 끝판왕은 에라토스테네스의 체를 쓰는 것입니다. 999983이라는 숫자가 소수인지 아닌지를 알아보려면 999983을 1부터 999982까지 모두 나누어보고 나머지가 있는지를 알 수 있습니다.

 

에라토스테네스의 체

'에라토스테네스의 체'의 핵심은 안해도 되는 연산은 하지 않는것 입니다. 어떻게 안하냐 하면 배수가 있는 숫자들을 차례로 지우는 것입니다.

 

예를 하나 들어보겠습니다. 999983은 이론적으로는 구십구만구천팔십삼번을 연산 해야 하지만 여기에서 반만 줄여도 속도가 2배 빨라지겠지요?

999983 / 2 999983 / 3 999983 / 4 999983 / 5 999983 / 6 999983 / 7 ....

 

일단 2를 제외한 2의 배수를 모두 지우면 2번째 숫자를 체에 걸러 낼 때는 2의 배수는 연산을 하지 않아도 됩니다.

999983 / 2 999983 / 3   999983 / 5   999983 / 7 ....

이렇게만 해도 두번째 부터는 연산이 절반으로 줄어듭니다.

 

계속해서 3을 제외한 3의배수 5를 제외한 5의배수의 연산을 모두 건너 뛰면 연산 해야 하는 양이 점점 줄어들어서 속도가 빨라집니다.

 

먼저 틀을 한번 잡아보겠습니다.

from math import sqrt
def sieve(n):
    ns = list(range(2, n + 1))
    
    i = 0 # ns의 index로 2, 3, 이렇게 갈 예정
    while ns[i] < sqrt(n): # 루트 n까지만 반복 하면 됨 50이라면 7까지
        i += 1
        print(sqrt(n), i)
    return ns
sieve(50)

위 코드는 아래 2가지 기능이 있습니다.

  1. 2부터 50까지 들어있는 배열 ns 만들기
  2. 루트 n보다 ns[i]가 작을때까지만 반복하기

그 다음 추가할 기능은 뒤에부터 반복하는 기능입니다.

from math import sqrt
def sieve(n):
    ns = list(range(2, n + 1))
    check = [True] * len(ns)
    
    i = 0 # ns의 index로 2, 3, 이렇게 갈 예정
    while ns[i] < sqrt(n):
        for j in range(len(ns), 0, -1):
            print(sqrt(n), i, ns[i], j, ns[j-1])
        i += 1
    return ns
sieve(50)

결과

7.0710678118654755 0 2 49 50
7.0710678118654755 0 2 48 49
7.0710678118654755 0 2 47 48
7.0710678118654755 0 2 46 47
7.0710678118654755 0 2 45 46

...중략...

7.0710678118654755 0 2 4 5
7.0710678118654755 0 2 3 4
7.0710678118654755 0 2 2 3
7.0710678118654755 0 2 1 2

...중략...

7.0710678118654755 5 7 4 5
7.0710678118654755 5 7 3 4
7.0710678118654755 5 7 2 3
7.0710678118654755 5 7 1 2

결과의 해석

루트 50은 7.0710... 입니다. 그래서 while문은 현재 0, 1, 2, 3, 4, 5 이렇게 총 6번 반복 됩니다. 왜냐하면 ns[i]가 루트 50보다 작을때까지 반복 하기 때문에 ns[5]는 7이라서 8부터는 반복을 하지 않습니다. 

 

그리고 for문에서는 j가 49번부터 0보다 큰 1까지 돌아갑니다.

 

print(sqrt(n), i, ns[i], j, ns[j-1])

신경써서 볼 것은 위 코드의 ns[j-1]이 부분 입니다. 결과에 마지막에는 50부터, 49.... , 2까지 ns에 있는 모든 숫자가 출력되고 있습니다. ns[j-1]이 실제 ns에 들어있는 숫자라는 것을 알 수 있습니다.

 

다음에는 이 ns[j-1]을 n[i]로 나누어서 나머지가 0이 아니면 나누어 떨어지는 것이므로 .pop()하는 로직이 들어갈 것입니다.

 

from math import sqrt
def sieve(n):
    ns = list(range(2, n + 1))
    i = 0
    while ns[i] < sqrt(n):
        for j in range(len(ns), 0, -1):
            print(sqrt(n), i, ns[i], j, ns[j-1])
            if ns[j-1] % ns[i] == 0: # 나누어 떨어지 확인해서 ns.pop(j)합니다.
                print(ns[j-1], ' will be poped.')
                ns.pop(j-1)
        i += 1
    return ns
sieve(50)

이제 ns.pop(j-1)하는 로직을 넣어보겠습니다.

 

결과

7.0710678118654755 0 2 49 50
50  will be poped.
7.0710678118654755 0 2 48 49
7.0710678118654755 0 2 47 48
48  will be poped.
7.0710678118654755 0 2 46 47
7.0710678118654755 0 2 45 46
46  will be poped.
7.0710678118654755 0 2 44 45
7.0710678118654755 0 2 43 44

... 중략...

44  will be poped.
7.0710678118654755 0 2 5 6
6  will be poped.
7.0710678118654755 0 2 4 5
7.0710678118654755 0 2 3 4
4  will be poped.
7.0710678118654755 0 2 2 3
7.0710678118654755 0 2 1 2
2  will be poped.
7.0710678118654755 1 5 24 49
7.0710678118654755 1 5 23 47
7.0710678118654755 1 5 22 45
45  will be poped.

... 중략...

 

결과의 해석

pop이 되기는 했습니다만 2  will be poped. 이 로그가 찍힌 것을 보면 2도 뽑혔습니다. 아마 3도 뽑히고 5도 뽑혔을 것입니다. 2, 3, 5는 소수이기 때문에 체에 거르지 말고 남겨놓아야 합니다.

 

for j in range(len(ns), 0, -1):

반복을 할 때 ns에 남아있는 모든 숫자를 반복 하는 것이 아니라 ns[i] 전까지 반복을 해야 합니다. 위 코드는 맨 뒤부터 맨 앞까지 모두 반복 하기 때문에 2, 3, 5 등이 뽑혀 나가는 것입니다.

 

for j in range(len(ns), i+1, -1):

위와 같이 고쳐 줍니다. 그러면 i가 0일때 i+1은 1이기 때문에 i가 0일때는 4까지 뽑히고 2는 남아있습니다.

마찬가지로 i가 1이면 ns[1]는 3입니다. 그래서 3을 제외한 3의 배수가 모두 .pop()됩니다.

 

완성된 코드

from math import sqrt
def sieve(n):
    ns = list(range(2, n + 1))
    i = 0
    while ns[i] < sqrt(n):
        for j in range(len(ns), i+1, -1):
            print(sqrt(n), i, ns[i], j, ns[j-1])
            if ns[j-1] % ns[i] == 0: # 나누어 떨어지 확인해서 ns.pop(j)합니다.
                print(ns[j-1], ' will be poped.')
                ns.pop(j-1)
        i += 1
    return ns
print(sieve(50))

python은 list가 pop(n)연산을 지원하기 때문에 위와 같이 해도 속도가 많이 올라갑니다.

 

결과

7.0710678118654755 0 2 49 50
50  will be poped.
7.0710678118654755 0 2 48 49
7.0710678118654755 0 2 47 48
48  will be poped.
7.0710678118654755 0 2 46 47
7.0710678118654755 0 2 45 46
46  will be poped.
7.0710678118654755 0 2 44 45
7.0710678118654755 0 2 43 44
44  will be poped.
7.0710678118654755 0 2 42 43
7.0710678118654755 0 2 41 42
42  will be poped.
7.0710678118654755 0 2 40 41
7.0710678118654755 0 2 39 40
40  will be poped.
7.0710678118654755 0 2 38 39
7.0710678118654755 0 2 37 38
... 중략 ...
7.0710678118654755 2 5 5 11
7.0710678118654755 2 5 4 7
7.0710678118654755 3 7 16 49
49  will be poped.
7.0710678118654755 3 7 15 47
7.0710678118654755 3 7 14 43
7.0710678118654755 3 7 13 41
7.0710678118654755 3 7 12 37
7.0710678118654755 3 7 11 31
7.0710678118654755 3 7 10 29
7.0710678118654755 3 7 9 23
7.0710678118654755 3 7 8 19
7.0710678118654755 3 7 7 17
7.0710678118654755 3 7 6 13
7.0710678118654755 3 7 5 11
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

 

결과의 해석

위 코드에서 while문은 총 6번 실행 되었습니다.

i가 0일때는 ns[i]는 2이므로 50, 48 ... 4 까지 뽑히고

i가 1일때는 ns[i]는 3이므로 45, 39 ... 9까지 뽑힙니다. 45다음에 39가 뽑힌것은 42는 2의 배수를 뽑을때 이미 뽑았기 때문이고 9까지 뽑힌 이유는 6은 앞에서 이미 뽑았기 때문입니다.

 

이렇게 해서 i는 3까지 가면 됩니다. 왜냐하면 앞에서 배수들은 모두 뽑히고 [2, 3, 5, 7, 11 ... ] 이렇게 남아있기 때문입니다.

 

그리고 리턴한 ns를 출력 해보면 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] 이렇게 50이하의 소수만 남아있습니다.

 

위 코드로 에라토스테네스의 체를 구현하면 총 98번이 돌아갑니다.

각 숫자마다 1부터 자신까지 계속 나누어본다면 연산 횟수가 훨씬 많았을 것입니다만 이정도로 줄인것입니다.

 

 

속도 개선

위 코드는 직관적으로 이해하고 단계별로 개선해 나가기 좋지만 연산이 중복되는 문제가 있습니다. 또한 나누기 연산을 계속 합니다. 하지만 에라토스테네스 체를 배열을 이용해 구했다면 나누기를 굳이 하지 않아도 됩니다.

 

from math import sqrt

def sieve(n):
    ns = list(range(2, n + 1))
    check =  [True] * len(ns)

    i = 0
    while ns[i] < sqrt(n):
        if check[i] == True:
            for j in range(i + ns[i], len(ns), ns[i]): # i는 check[i]가 True일 때만 연산합니다.
                check[j] = False
        i += 1

    r = []
    for c in range(len(check)):
        if check[c]:
            r.append(ns[c])

    return r

print(sieve(1000000))

[Done] exited with code=0 in 0.736 seconds

 

위 코드는 100만이하의 모든 소수를 구했지만 1초도 걸리지 않았습니다.

 

위 코드가 이전 코드보다 간단해 보이지만 이전 코드를 이해하지 못하면 막상 구현해내기가 쉽지 않습니다. 이유는 while문 안에 있는 for문을 어디서부터 어디까지 얼마나 반복할 것인지를 떠올리기가 어렵기 때문입니다.

 

 

 

end.

728x90
블로그 주인장입니다. 원하시는 정보는 얻으셨나요? 이 포스트에서 추가로 필요한 정보가 있으시면 여기에 남겨주세요.