Orchemi

Orchemi

I start where others stop.

[Algorithm] 소수 구하기: 에라토스테네스의 체

작성:    

업데이트:

카테고리:

태그: ,

BOJ #1929

이번 소수를 구하는 알고리즘에 대한 포스트는 BOJ #1929의 문제를 해결하는 과정에서 알게된 사실을 기록하는 용도이다. 문제 풀이 과정과 탐구는 [BOJ][⚪2][백준#01929] 소수 구하기 링크를 참고한다.


소수 구하기?

그동안 문제의 풀이는 단순히 소수의 정의에 의거한 풀이를 해왔다. 소수(Prime Number)의 정의는 ‘약수로 1과 자기 자신만을 가지는 수’이다. 그래서 수의 처음부터 끝까지 조회한 뒤 어떤 수로 나누었을 때 나머지가 0이 되는, 즉 약수가 2개가 넘는 수는 소수에서 제외하는 방식으로 문제를 풀어왔다.

그런데 이번 BOJ 문제는 그렇게 풀면 무조건 시간 초과가 나오는 방식이었기 때문에 문제를 끝끝내 해결할 수 없었고 인터넷을 참고하다가 알게된 소수 구하기 알고리즘이 있다.


에라토스테네스의 체

출처: 위키피디아

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법으로, 다음의 과정을 통해 소수를 구한다.

FRONT

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


이를 프로그래밍 언어로 표현하면 아래와 같다. 친절하게도 위키피디아에서 직접 코드를 제시해주었다. 파이썬 언어 외에도 C++과 Java, Haskell 버전이 있다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

그리고 그 결과이다.

prime_list(20)
[2, 3, 5, 7, 11, 13, 17, 19]

max(prime_list(1000000))
999983

즉, 1차원 배열로, n까지의 수만큼 True를 리스트에 넣고, n의 최대 약수인 int(n ** 0.5)를 m에 할당한 뒤, 2부터 m까지(range(2,m+1)) 각 수를 인덱스로 간주하여 리스트를 주욱 조회한다.

그러다가 특정 인덱스에서 True, 즉 소수를 발견하면 해당 인덱스의 2배부터 시작해 인덱스의 간격만큼 리스트를 조회하여 False 처리한다. 이는 해당 인덱스의 배수에 대해 n까지 계속 False 처리를 하며 소수가 아닌 수를 제거해주는데, sieve[i] 그 자신까지 제거가 되면 안 되기 때문에 자신은 제외하기 위함이다.

이후 2부터 n의 수에 대하여 True인 수만 따로 빼내어 반환하면 되는 것이다.

꽤나 복잡해 보이므로 BOJ에서 에라토스테네스의 체로 문제를 푼 사람의 답안을 살펴보겠다.


모범 답안 : 에라토스테네스의 체

출처

import sys
a,b=map(int,sys.stdin.readline().split())
def p(n):
    p=[True]*n
    for i in range(2,int(n**0.5)+1):
        if p[i]==True:
            for j in range(i+i,n,i):
                p[j]=False
    return [i for i in range(2,n) if p[i] == True]
print(*sorted(list(set(p(b+1))-set(p(a)))),sep='\n')

연산 시간 320ms 기록한 답안이다. 물론 sys 모듈을 import하고 sys.stdin.readine()을 사용해 입력 자체도 빠르게 하려고 했겠지만, 무엇보다 로직이 연산 시간을 줄이는 데에 지배적인 역할을 했을 것이다.

밑에 print() 문을 제외하고는 위키피디아의 에라토스테네스의 체 로직과 흡사하다. 맨 마직에 set으로 리스트를 형변환한 이유는 위의 문제는 n까지의 소수만 구하는 것이 아니라, a와 b 사이의 수에서 소수를 구하는 것이기 때문이다. 그래서 차집합을 이용하기 위해 set을 이용한 것이다.

어차피 set의 차집합을 list로 다시 형변환한 뒤, sorted() 함수를 사용하여 정렬할 것이라면 리스트의 del을 사용하는 것은 어떤가하는 생각도 들었다. 시간 복잡도에 대한 우위를 가릴 실력은 되지 않기 때문에 뭐가 더 시간적, 공간적으로 효율적인 방법인지는 모르겠다.

리스트를 print()문과 sep=’\n’ 을 이용해 한 줄씩 출력하는 방식은 잘 생각하신 것 같다.


모범 답안 : 제곱근만 사용

출처

x, y = map(int, input().split())

for i in range(x, y+1):
    if i == 1:
        continue
    for j in range(2, int(i**0.5)+1 ):
        if i%j==0:
            break
    else:
        print(i)

에라토스테네스의 체를 사용하지는 않지만 제곱근까지만 수를 조회해서 소수를 출력한다는 점에서 편리함을 느꼈던 코드이다. 리스트를 사용하지 않기 때문에 더 빠를 것이라 생각했지만 연산시간은 5920ms가 나왔다.

이는 아무리 제곱근까지만 조회한다고 하더라도 for문을 두 번씩 모두 돌리기 때문으로 y값이 커질수록 그 연산 속도는 더 커질 것이다.

앞으로 소수 구하기 문제를 푸는 경우 에라토스테네스의 체를 적극 활용하도록 하자.

댓글남기기

참고