[백준 - python] 17103번: 골드바흐 파티션

문제 링크

17103번: 골드바흐 파티션

문제 풀이

from sys import stdin

input = stdin.readline

primes = [True for _ in range(1000001)]
for i in range(2, 1000001):
    if primes[i] == True:
        for j in range(i*2, 1000001, i):
            primes[j] = False

T = int(input())

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

17103 입출력 예시

*key point: 에라토스테네스의 체를 이용하여 미리 주어진 범위에서 소수를 판별할 수 있는 리스트를 만들어 활용한다. 만약 호출할 때마다 소수를 판별하는 함수를 만들어 활용하는 경우 시간 초과가 발생한다.