[Baekjoon]백준 17103 골드바흐 파티션(실버 2) - Python

문제설명

문제를 읽어보면 입력받은 수를 만드는 두 소수 쌍의 개수를 찾는 문제이다 

예를 들어보면 5의 경우 (1, 4), (2, 3) 두 가지의 합으로 나타낼 수 있는데

1, 4의 경우 둘 다 소수가 아니므로 제외되고 2, 3의 경우에는 둘 다 소수이므로 count에 포함되어 1이 출력된다

10을 예를 들어보면 (1, 9), (2, 8), (3, 7), (4, 6), (5, 5)로 나타낼 수 있는데

(3, 7), (5, 5) 두 가지의 경우가 존재하므로 2가 출력되게 된다

 

이전에 만들어둔 코드를 활용하여 이 문제를 해결하기위한 코드를 처음에 작성하였다

def Is_prime(num):
    if num == 1:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

T = int(input())

for _ in range(T):
    n = int(input())
    cnt = 0
    for i in range(1, n//2 + 1):
        if Is_prime(i) and Is_prime(n - i):
            cnt += 1
    print(cnt)

그랬더니 시간초과가 발생하였다. 

그래서 이번에는 혹시나해서 다른 방식으로 작성을 해보았다

이전 문제에서 미리 소수인지를 저장한 리스트를 하나 만들어두고 그 리스트에 값이 존재하는지

확인하는 로직으로 코드를 작성하였다

def Is_prime(num):
    if num == 1:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

prime = []
for i in range(1, 10001):
    if Is_prime(i):
        prime.append(i)

T = int(input())

for _ in range(T):
    n = int(input())
    cnt = 0
    for i in range(1, n//2 + 1):
        if i in prime and n - i in prime:
            cnt += 1
    print(cnt)

그러나 이번에도 시간초과가 발생하는 것을 보고 '아 소수 판별 함수 존재자체가 문제가 발생하나?'

라는 생각이 들어서 이전 문제들의 코멘트를 살펴보니 

에라토스테네스의 체를 써서 소수를 구하는 방법이 존재한다는 것을 알 수 있었다

이는 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는 가장 간단하고 빠른 방법이다

 

에라토스테네스의 체의 원리 자체는 간단하다 예를 들어 1부터 100까지의 범위에서 소수임을 확인할 떄 

먼저 1을 삭제한다 이후에 2부터 확인을 시작하는데, 2의 배수는 모두 삭제하고, 다음은 3의 배수를 모두 삭제해나간다

즉, 리스트에 존재하는 값을 하나씩 증가하며 그 수의 배수는 모두 삭제하는 전략이다 

4의 경우에는 2의 배수라 이미 삭제되었으므로 5의 배수도 모두 삭제하는 방식이다

이렇게 확인을 하다보면 2, 3, 5...97 과 같은 소수만 범위내에 남게된다

 

이번엔 그 로직을 사용하여 n의 범위만큼 리스트를 만들어 값을 저장하고 리스트를 확인하여

값을 출력하도록 작성하였더니 드디어 정답임을 확인할 수 있었다

import sys

prime = [False] * 2 + [True] * 999999

for i in range(2, 1000001):
    if prime[i]:
        for j in range(i*2, 1000001, i):
            prime[j] = False
            
T = int(sys.stdin.readline())

for _ in range(T):
    cnt = 0
    n = int(input())
    for i in range(2, n//2 + 1):
        if prime[i] and prime[n - i]:
            cnt += 1
    print(cnt)

시간초과로 꽤나 골치가 아팠지만 에라토스테네스의 체에 대해 알게된 좋은 기회였다고 생각한다