[백준] 17103번: 골드바흐 파티션 파이썬

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

골드바흐 파티션 문제는 짝수 \( n \)을 두 소수의 합으로 표현하는 방법의 개수를 찾는 문제이다. 골드바흐의 추측에 따르면, 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있다. 이 문제에서는 주어진 짝수 n 에 대해, 두 소수의 합으로 n을 나타내는 모든 경우의 수를 찾아 출력하는 게 목표이다.

 

처음에는 단순하게 for문으로 순서대로 돌면서 n-i와 i가 둘 다 소수인지 판별하도록 코드를 짰다.

그런데 시간초과에 걸렸다.

그래서 미리 1000000까지의 소수를 배열에 저장해놓고 배열을 체크하는 식으로 구현했다.

 

코드 풀이

import sys
import math

def is_primenum(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

list = [False] * 1000000
for i in range(1, 1000000):
    if is_primenum(i):
        list[i] = True

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    num = 0
    for i in range(1, n//2 + 1):
        if list[n - i] and list[i]:
            num += 1
    print(num)

1.  `is_primenum` 함수는 주어진 수가 소수인지 아닌지를 판별.
2. 1부터 1,000,000까지의 소수를 미리 계산해 `list`에 저장. 소수면 `True`, 소수가 아니면 `False`로 표시.
3. 테스트 케이스마다 n 을 입력받고, i 와  n-i 가 모두 소수인 경우를 찾아 그 개수를 세어 출력.