알고리즘 기초 - 소수의 판별(에라토스테네스의 체)

반응형

소수란, 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말합니다.

어떤 자연수 n이 소수인지 판별하는 가장 기초적인 함수 코드는 아래와 같이 작성할 수 있습니다.

def is_prime(n):
    for i in range(2, n):
        if n%i==0: 
            return False  ## 소수 아님
    return True

2부터 n-1까지의 모든 수로 n을 나누어보는 방법입니다. 만약 나누어 떨어지는 수가 있다면 소수가 아닌게 되겠죠? 그럼 False를 리턴합니다. 그러나 이런 방법은 n까지의 모든 수를 확인해야 하기 때문에 시간복잡도는 ​O(n)​입니다. 따라서, n이 매우 크다면 비효율적이게 됩니다.

​

좀 더 개선된 방법을 적용한 코드는 아래와 같이 작성할 수 있습니다.

import math
def is_prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n%i==0:
            return False  ## 소수 아님
    return True

 

n의 제곱근까지만 확인해주면 됩니다. n=16일때를 예로 들어보겠습니다. 약수인 1, 2, 4, 8, 16에 대하여 가운데 약수인 4를 기준으로 대칭적으로 2개씩 앞뒤의 숫자를 곱하면 16을 만들 수 있습니다. 따라서, 모든 수를 확인하는게 아닌 sqrt(n)까지만 계산해주면 됩니다! 이 방법은 시간복잡도 O(n^(1/2))입니다.

​

=> 그럼 수의 범위가 주어졌을 때, 그 수 까지의 모든 소수를 찾아야 하는 경우에 가장 빠른 방법은 무엇일까요?

​

​

▶ 에라토스테네스의 체

고대 그리스의 수학자로 유명한 에라토스테네스가 만들어낸 방법입니다. 이 알고리즘은 수의 범위가 주어지면 범위내의 여러 개의 수가 소수인지 아닌지를 판별할 때 사용할 수 있습니다. n보다 작거나 같은 모든 소수를 찾고싶을 때 사용할 수 있습니다. 이 알고리즘의 작동 방식은 아래와 같습니다.

1. 2부터 n까지의 모든 자연수를 나열해줍니다.

2. 남아있는 수들 중에서 아직 처리하지 않은 가장 작은 수를 찾습니다. 이를 i라 하겠습니다.

3. 남은 수 중에서 i의 배수를 모두 제거해줍니다.(이때, i는 제거하지 않고 남겨둬야합니다.)

4. 더 이상 반복할 수 없을 때까지 2-3 과정을 반복합니다.

이 과정을 그림으로 좀 더 쉽게 확인해보겠습니다. n=26이라고 하겠습니다.

step 1) 2부터 26까지 모든 자연수를 나열합니다.

step 2) 남은 수들 중에서 아직 처리하지 않은 가장 작은 수를 찾습니다. 그 수를 제외한 배수들을 모두 제거해줍니다. 첫번째로 2를 제외한 2의 배수를 제거해주면 됩니다.

step 3) 다음 위의 과정을 다시 반복합니다. 아직 처리하지 않은 가장 작은 수를 찾습니다. 그 수를 제외한 배수들을 모두 제거해줍니다. 두번째로 3이 대상이 되겠습니다.

step 4) 그 다음은 5를 제외한 5의 배수를 모두 제거합니다.

step 5) 이 과정을 모두 거치고 남아있는 수들은 위 그림과 같습니다. 이 수들은 모두 소수에 해당합니다!

​

이 알고리즘의 코드는 아래와 같이 구현할 수 있습니다.

import math
n=1000
arr=[True for i in range(n+1)] 

for i in range(2, int(math.sqrt(n))+1): # 2부터 n제곱근까지의 수 모두 검사
    if arr[i]==True: # i가 소수 일때
        # i를 제외한 모든 배수 삭제
        j=2 
        while i*j <= n:
            arr[i*j] = False
            j+=1
            
# 모든 소수 출력
for i in range(2,n+1):
    if arr[i]:
        print(i,end=' ')

 

위 코드를 통해 찾은 1000까지의 모든 소수는 아래와 같습니다.

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

=> 이 알고리즘은 O(nloglogn)의 시간복잡도를 갖습니다. 수들을 나열할 별도의 메모리가 필요하기 때문에, 10억과 같이 아주 큰 수가 주어진다면 이 알고리즘을 이용하기는 어렵습니다. 따라서 n이 1,000,000이내의 수가 주어졌을 때 가장 사용하기 적합하다고 합니다.