[알고리즘][Python] 백준(BOJ) 17103 골드바흐 파티션_파이썬

 

17103 골드바흐 파티션    www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

 

문제 풀기 전 공부할 것 : 수학, 정수론, 소수 판정, 에라토스테네스의 체

 

 

 

 

 

 

 

풀이

<내용>

• 모든 테스트 케이스를 입력받는다.
• 테스트 케이스에서 가장 큰 값을 기준으로 소수를 찾는다.
• for문을 돌면서 두 소수의 합이 해당 정수인 경우 개수+1을 한다.
• 모든 경우를 찾고 출력한다.

 

 

<코드>

import sys
input = sys.stdin.readline

t = int(input())
nums = [int(input()) for _ in range(t)]
m = max(nums)

prime = [False, False] + [True] * (m-1)
for i in range(2, int(m**0.5)+1):
    if prime[i]:
        for j in range(i+i, m+1, i):
            if prime[j]:
                prime[j] = False
                
for num in nums:
    cnt = 0
    for i in range((num//2)+1):
        if prime[i] and prime[num-i]:
            cnt += 1
    print(cnt)