[알고리즘] 에라토스테네스의 체 알고리즘 - Python(백준 2581)

안녕하세요 여러분:)

이번시간에는 에라토스테네스의 체 알고리즘에 대해 알아봅시다.

에라토스테네스의 체는 유클리드 호제법과 더불어 알고리즘을 공부하셨다면,

한 번쯤은 들어봤을 알고리즘이죠? ㅎㅎ.

 

---

 

1. 에라토스테네스의 체란?

에라토스테네스의 체란 간단하게 말해서 시작범위와 끝 범위의 수가 주어졌을 때 그 수 가운데 있는 수 중에서 소수 리스트를 구할 수 있는 알고리즘입니다!

 

기본적으로 1부터 100까지 수 중에서 소수를 구하여라.라는 문제가 주어졌을 때 우리는 한 수에 대해서 모두 이중 반복문을 돌려서 1과 자기 자신을 포함한 약수가 어떤 수가 있는지 구하는 방법이 있죠?

 

그런데 이 방법을 사용하면 모든 수에 대해서 이중 반복문을 돌려야 하므로 시간 복잡도가 O(n²)으로 매우 큽니다.

이때 에라토스테네스의 체 알고리즘을 사용한다면 훨씬 더 효율적으로 범위 내의 소수 리스트를 구할 수 있습니다.

 

 

2. 알고리즘의 핵심 개념

이 알고리즘의 핵심개념의 핵심개념을 설명하기 전에 알아야할 개념부터 정리하면 아래와 같습니다.

시작범위부터 K 사용하려면 두 가지 개념만 이해한다면 간단하게 구현할 수 있습니다.

• 입력 : A<=x<=B (A가 시작하는 수, B가 끝나는 수)
• 출력: A와 B 사이에 있는 소수 리스트 
• 최대 범위 수(K): B이내의 제곱 수 에서 최댓값 ( K²<=B)
• 범위 내에서 각 숫자의 최대 배수(M): B를 x로 나눈 몫 (B//x) 

예시로 입력과 출력은 1부터 120까지 주어지면 1이 A, 120이 B가 된다. 그리고 출력은 1과 120 사이에 있는 소수 리스트이다. 그리고 최대 범위 수란 마지막 범위의 수 B보다 작은 최대 제곱 수라고고 보면 된다. 예시에서는 B가 120이므로 120 이내의 수 중에서 최대 제곱수는 11²=121이 최대 제곱수 이므로 여기서 11이 최대 제곱수이다.

여기까지 이해했으면 거의 끝났다. 이 알고리즘의 핵심 개념은 아래와 같다.

 

입력이 주어졌을 때 A부터 K까지 반복문을 돌려서 각 수가 소수와 소수가 아닐 때 아래와 같이 처리하면 된다. 왜냐하면 소수라도, 그 배수는 모두 소수가 아니기 때문이다. 

• 소수라면:  그 수만 소수 리스트에 넣고, 그 배수는 소수가 아닌 수에 넣는다.
• 소수가 아니면: 그 수와 그 수의 배수 모두 소수가 아닌 수에 넣는다. 

이 방법을 이용해서 A부터 K까지 반복문을 돌리고 남는 수는 모두 소수 리스트에 추가하면 빠르게 범위 내의 수 중에서 소수 리스트를 구할 수 있다. 위 예시에서는 1부터 120까지의 수 중에서 최대 범위 수는 11이므로 1부터 11까지 반복문을 돌려서 소수인지 판별한 뒤, 위 로직과 같이 처리하면 된다. 이때 1부터 11까지 반복문을 돌릴 때 3 소수인지 판별하고 배수를 모두 소수가 아닌 수로 처리하면 된다.

출처: 위키백과 에라토스테네스의 체

그리고 이 방법을 11까지 반복하고 나면 남은 수는 모두 소수가 된다! 이때 위 용어정리에서 최대 배수 M이란 3을 기준으로 120까지의 범위에서는 3x1, 3x2~ 3x40=120까지 진행이 가능하므로 이때 40이 최대 배수가 된다. 이 수를 구하면 더 효율적으로 반복문을 돌릴 수 있으며, 이 수는 마지막 범위의 수 B에 해당 수 (3)을 나누면 된다. (120//3==40) 여기까지 이해했으면 모두 끝났다. 

 

3. 구현 방법과 코드

이 알고리즘의 개념은 위와 같고 구현할 때는 처음 입력을 받을 때 범위 내의 숫자에 해당하고 True로 초기화된 Boolean  배열을 만든 뒤, 반복문을 돌리며 소수가 아닌 수를 False처리하면 최종적으로 남은 True인 숫자는 모두 소수가 되므로 아래 코드를 이용하면 편리하게 할 수 있다. 이 코드는 1부터 100까지 주어졌을 때 그 사이 소수를 구하는 알고리즘이다. 

M=int(input())
N=int(input())
#M<=N - N이 더 크다, 소수 리스트를 찾아야
arr=[True]*(N-M+1)
lastRange=int(N**0.5) # 마지막 범위의 수에 0.5를 제곱하면 루트를 씌우는 것
for num in range(2,lastRange+1):
    primeCheck=0
    maxDrain=int(N/num) # 최대 배수
    # num이 소수인지 체크
    for i in range(2,num+1):            
        if num%i==0:
            primeCheck+=1

    if primeCheck==1: # 해당 num이 소수라면 그 수만 True, 그 수의 배수는 False로 설정
        arr[num-1]=True
        for i in range(2,maxDrain):
            arr[(num*i)-1]=False

    else: # 해당 num이 소수가 아니라면 그 수도 False 그 배수를 모두 False로 설정
        for i in range(1,maxDrain):
            arr[(num*i)-1]=False

primeList=[i-1 for i in range(2, N-M+1) if arr[i] == True]
print(primeList)

그리고 나 같은 경우는 maxDrain이란 변수를 만들어서 각 수의 배수도 False로 처리하도록 구현하였는데 이 방법 말고도 for i in range(2, lastRange+1, num) 이런 식으로 num의 단위로 반복하는 방법도 있다.

 

 

4. 백준 2581 소수 구하기 풀이 

https://www.acmicpc.net/problem/2581

2581번: 소수

그리고 관련 문제는 백준의 2581번이 있는데 이 문제는 푸는데 좀 헤매었다. 왜? 입력으로 주어지는 범위가 1부터 100이 아니라 60부터 100과 같이 주어졌을 때 어떻게 처리할지 고민하느라 많이 헤멨다. 근데 결론은 시작 범위가 더 크게 주어져도, 우선 소수를 구할 때는 마지막까지의 범위만 보고 그 사이 소수를 구한 다음, 결과를 출력할 때 시작 범위부터 마지막 범위까지만 잘라서 출력하는 매우 효율적인 방법이 있었다!

 

아래 코드 풀이에서 가장 핵심이 되는 부분은 이중 반복문에서 for y in range(x+x, M+1, x)인데 이 부분이 정말 예술인 것 같다. 이 코드의 뜻은 루트 M만큼 반복하면서 그 처음 그 수는 건너뛰고 그다음 배수(x+x)부터 x 간격으로 모두 False로 설정하는 코드인데 처음 이 코드를 봤을 때는 이렇게 코드를 짜면 1-10 이내에 범위들은 소수 그냥 건너뛰니까 소수가 다 안 구해지지 않을까 라는 생각을 했는데 디버깅을 해보니 아니었다! 

N = int(input())
M = int(input())
lis = [False,False]+[True for i in range(2,M+1)] # 시작 범위에 관계 없이 마지막 범위까지 리스트를 만들고, 0-1번째 인덱스는 False처리
big = int(M** 0.5) 
for x in range(2, big+1):
    if lis[x] == True:
        for y in range(x+x , M+1, x) : 
            lis[y] = False

result = [x for x in range(N,M+1) if lis[x]== True] # 그리고 시작 범위에 대한 처리는 결과를 출력할 때 앞부분을 시작 범위로 잘라버리기 

if len(result)==0:
    print(-1)
else:
    print(sum(result))
    print(min(result))

 

 

아래는 시작범위로 60, 마지막 범위로 100을 입력한 예시이다. 보면 바깥 반복문에서 2부터 10까지 반복하는데  x=2로 처음 반복할 때 lis [x]가 True여서 안의 반복문에 들어오는데 여기서 x의 배수부터 x단위로 건너뛰면서 x의 배수를 모두 False처리하는데 여기서 x=2의 배수인 2,4,6,8을 모두 False처리를 하길래 감탄했다.  이러면 1-10 이내의 약수도 모두 깔끔하게 False 처리가 되어  이 알고리즘을 끝까지 돌리면 주어진 범위 내의 소수를 아주 깔끔하게 구할 수 있다.  

 

5. 소수 구하기 알고리즘에서 쓰인 핵심 아이디어

이상으로 소수 구하기에서 매우 자주 사용되는 에라토스테네스의 체 알고리즘을 사용해 봤다. 그리고 여기 핵심 아이디어는 아래와 같다. 

• 주어진 범위 (a, b) 내의 소수를 구하기 위해서는, 우선 끝나는 범위(b)까지의 모든 소수를 구한 뒤, 마지막에 해당 범위인 시작 범위(a)부터 끝나는 범위(b)까지만 잘라주면 된다.
• 배수를 False 처리할 때는 2부터 끝나는 범위까지 x의 배수의 모두 x단위로 건너뛰면서 False 처리해준다. (for y in range(x+x, b+1, x) 
• 소수는 약수고가 1과 자기 자신밖에 없는 수이므로 이를 판단할 때 (2, b)까지 잡고 반복문을 돌리고, 그 사이에 약수가 존재하면 소수가 아니라는 아이디어. 

이상 에라토스테네스의 체 알고리즘을 사용하는 방법에 대해 알아봤다!. 이제 소수 나오기 문제는 잘 풀 수 있어야 한다.

참고로 에라토스테네스의 체 알고리즘을 사용하지 않고도 아래와 같이 2581번 문제를 풀 수 있다.

a=int(input())
b=int(input())
n_list=[]

for i in range(a,b+1):
    if i == 2:
        n_list.append(i)
    else:
        for j in range(2,i): #에라토스테네스의 체가 아니라 그냥 하나씩 다 나눠서 구하는 방법
            if i%j == 0:
                break
            elif j == i-1: # 마지막 턴에서까지 약수가 없어서 break가 안 됐으면 소수리스트에 추가
                n_list.append(i)

if len(n_list)==0:
    print(-1)
else:
    print(sum(n_list))
    print(min(n_list))

 

 

 

---

 

그럼 여기까지 에라토스테네스의 체에 대해 알아봤다. 항상 알고리즘을 공부하는 것을 활용하기 위해 하는 것이다.

따라서 이렇게 정리하고 이해하였으면, 다음에 "소수 구하기" 비슷한 키워드가 나왔을 때 비슷하게 구현하여

활용하는 것이 가장 중요하다. 그럼 20000..