백준 Python 17103 골드바흐 파티션

문제 링크

• 에라토스테네스의 체 위키피디아
• 가장 큰 입력값 이하의 수들에 대한 소수 여부를 담은 리스트를 만들면 된다.

t = int(input())

def prime_list(n):
    sieve = [True] * (n + 1)
    
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] == True:
            
            for j in range(i + i, n + 1, i):
                sieve[j] = False
                
    return sieve

nums = []

for _ in range(t):
    nums.append(int(input()))
    
max_num = max(nums)
primes = prime_list(max_num)

for num in nums:
    cnt = 0
    
    for i in range(2, num // 2 + 1):
        if primes[i] and primes[num - i]:
            cnt += 1
                
    print(cnt)