17103 골드바흐 파티션 _python

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

17103번: 골드바흐 파티션

골드바흐의 추측 문제

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

문제 그대로의 뜻인데, 어려운 문제는 아니다.

 

문제 접근

우선 소수를 활용해야 되는 문제인데, 입력을 받을 때 마다 소수를 확인한다면 시간초과가 날것이다.

1,000,000을 100,000번 입력받으면 연산이 너무 많아질 것이다.

그러면 소수를 미리 확인을 해두고 접근하는 방식을 써야하는데, 소수를 확인하기 위해선 에라토스테네스의 체를 활용하면 된다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

위키에 있는 gif를 가져왔다.

소수의 모든 배수를 제거해나가는 방식.

2의 배수를 모두제거 -> 3의 배수를 모두 제거 -> 5의 배수를 모두제거 ...

범위까지 반복하면 된다.

 

이러면 소수만 확인가능한 배열이 있을 것이고,

이 배열의 i번째 소수만 참고해서 i와 N-i가 소수이면서, i와 N-i의 합이 N이 되는 경우의 개수를 세면 된다.

 

코드

import sys
input = sys.stdin.readline

#소수 골라내기 (에라토스테네스의 체 활용)
primeNum = [False, False] + [True]*999999

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

T = int(input())

#문제 풀이
for i in range(T):
    count = 0
    N = int(input())
    for j in range(2, N//2+1):
        if primeNum[j] and primeNum[N-j]:
            count += 1
    print(count)