백준 6588번 파이썬 feat.에라토스테네스의 체

 

6588번: 골드바흐의 추측

주어진 짝수를 소수인 홀수 두 수의 합으로 나타내는 문제

소수인지 확인하는 방법이 시간초과 문제를 발생시키냐 달려있다!! 유명한 소수찾기 방법 에라토스테네스의 체에 대해서 알아보자.

n 이하의 소수를 찾는다고 하자

n = int(input())
a = [True] * (n + 1)
m = int(n**0.5)

for i in range(2, m + 1):
    if a[i] == True:
        for j in range(i + i, n + 1, i):
            a[j] = False

print([i for i in range(2, n + 1) if a[i] == True])

배열을 주어진 수 n + 1 만큼 모두 True로 할당하고, 어떤 수의 배수가 되는 모든 수를 찾아 False로 할당하는 것이다. 이런식으로 배열을 이용해서 미리 소수판별을 해놓으면 소수확인시 값을 가져오기만 하기 때문에 O(1)시간복잡도가 걸려서 시간초과를 피할 수 있다.

n의 제곱근 만큼만 반복하고, 주어진 수 2부터해서 2의 배수, 3의 배수 index의 배열에는 False 즉, 소수가 아니라고 할당을 해주는 방식이다.

이를 이용해서 6588번 문제를 풀어보면,

코드

array = [True for i in range(1000001)]
#에라토스테네스 체
for i in range(2, 1001):
    if array[i]:
        for k in range(i + i, 1000001, i):
            array[k] = False

while True:
    n = int(input())
    if n == 0:
        break

    for i in range(3, len(array)):
        if array[i] and array[n - i]:a
            print("%d = %d + %d" %(n, i, n - i))
            break

100만까지 수가 주어질 수 있고, 반복은 100만의 제곱근인 1000번까지 반복하여, 소수가 아닌 수를 체크한다.

제일 작은 소수이자 홀수인 3부터 시작하여 소수판별을 할당해놓은 array에서 반복문 i 와 n - i 가 소수인지 확인한다.

바로 break을 쓰는 이유는 답이 여러개라면, n = a + b 두 수 a, b의 차이가 최대인 경우를 출력하므로, 

작은 수 3부터 시작하여 체크하기 때문에 처음 나오는 경우가 바로 두 수의 차이가 최대인 경우이다.