에라토스테네스의 체

코딩 문제를 풀다보면 소수와 관련된 문제가 나온다.

예를 들어, '자연수 2 ~ 100 범위에서 소수를 출력하라' 라는 문제가 나온다면

prime = []
for i in range(2, 101):
    flag = 0
    for j in range(2, i):
        if i % j == 0:
            flag = 1
            break
    if flag == 0:
        prime.append(i)
print(prime)

[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]

위와 같이 반복문을 돌면서 i가 2 이상의 어떠한 값에 나머지 연산을 했을 때 값이 0이 나오는지 체크하면 된다.

 

하지만 이렇게 코드를 짜면 100,000까지의 소수를 찾으라고 하면 총 연산 횟수가 100,000 x 100,000번으로

시간초과가 난다.

실행시간은 아래와 같으며 각각 100, 1,000, 10,000, 100,000까지의 소수를 구할 때 걸리는 시간이다.

PS C:\Users\이재정> python .\test.py
time :  0.0

PS C:\Users\이재정> python .\test.py
time :  0.004964113235473633

PS C:\Users\이재정> python .\test.py
time :  0.3909595012664795

PS C:\Users\이재정> python .\test.py
time :  32.64931774139404

 

백준에서 소수와 관련된 문제를 풀 경우 P(4 ≤ P ≤ 10^100)과 같은 범위가 출제되기 때문에 위와 같은 방법으론

한계가 있다.

이럴 때 사용하는 Algorithm이 에라토스테네스의 체 이다.

구현 방법은 아래와 같다.

1. 범위 2 ~ n이 주어지면 n개의 요소가 담긴 리스트를 생성한다.
2. 반복문을 돌면서 i의 배수를 리스트에서 제거해준다.

 

설명만 보고서는 이해가 안 가니 직접 코드를 통해 확인한다.

예를 들어 2 ~ 100 까지의 범위에서 소수를 구하는 방법을 단계별로 구현해보자.

 

n으로 100이 주어진다.

 

arr[0], arr[1]은 False로 고정인데 소수의 정의를 보자면

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

이므로 0과 1은 당연히 고려할 범위에서 제외된다.

0, 1을 False로 나머지는 True로 초기화해주며 0 ~ 100에서 0, 1을 제외하면 총 99개가 되기 때문에

n - 1개의 True가 arr에 속하게 된다.

n = 100
arr = [False, False] + [True]*(n-1)

 

첫 번째 for문의 경우 2 ~ 100 까지 반복문을 돌리기 위해 n+1까지 반복한다.

어떤 수의 배수가 되는 수는 소수가 될 수 없기 때문에 i를 먼저 append 시키고서 두 번째 for문에서

i의 모든 배수를 False로 바꿔준다.

예를 들어 i가 2일 때 range(2*i, n+1, i)를 통해 2, 4, ... 98, 100까지의 모든 2의 배수는 False가 된다.

i가 3일 땐 3, 6, 9, ... , 99까지의 수가 False, 4일 땐 4, 8, ... 100

prime = []

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

 

이런 식으로 배수를 찾게 되고 prime에는 배수가 없는 소수만 남게 된다.

print(prime)

[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]

 

이 알고리즘을 바탕으로 백준의 1837번 문제를 풀어보자.

< 출처 : 백준 홈페이지 >

 

핵심은 먼저 K보다 작은 소수가 담긴 list인 prime을 구하고,

prime의 요소가 P와 나머지 연산하여 0이 되는 값이 있는지 확인하는 것이다.

최종 코드는 아래와 같다.

에라토스테네스의 체 를 통해 K보다 작은 소수를 찾고, P가 i로 나뉘어지는지 체크하면 된다.

P, K = map(int, input().split())

prime = []
arr = [False, False] + [True]*(K-1) #K보다 작은 소수 찾기

for i in range(2, K):
    if arr[i]:
        prime.append(i)
    for j in range(2*i, K, i):
        arr[j] = False

result = "GOOD"

for i in prime:
    if P % i == 0:
        result = "BAD " + str(i)
        break
print(result)