[백준 17103] 골드바흐 파티션 (python)

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

17103번: 골드바흐 파티션

골드바흐 파티션 문제

짝수 N이 주어졌을 때 두 소수의 합으로 나타낼 수 있는 경우의 개수를 세는 문제

에라토스테네스의 체를 이용해서 해결 할 수 있었다.

📌문제 접근 포인트

1. 테스트케이스만큼 반복해서 숫자를 탐색해야 하므로, 미리 소수의 리스트를 만들어서 찾는 게 시간을 줄일 수 있다.
2. 에라토스테네스의 체를 이용해서 소수 리스트를 만들어주고 탐색을 해보자.
3. 숫자를 찾을 때, 두 소수의 순서가 다른 갯수만 찾아야 하므로 N/2까지만 탐색하면 된다.. 예를 들어 30이란 숫자는 [7 23] [11, 19] [13 17] [17 13] [19 11] [23 7] 이렇게 6개로 구성되어 있지만, 30의 절반인 15 이하에서 [7 23] [11, 19] [13 17] [17 13] 를 찾고 나면 뒤에 숫자는 동일한 숫자인 것을 알 수 있다.
4. N의 골드바흐 파티션은 소수 a와 N에서 a를뺀 N-a가 소수일 경우 만족한다고 볼 수 있으니, 조건에 맞게 찾아 개수를 세어주자

⚙ 내가 푼 정답코드

def prime(n): #에라토스테네스의 체로 소수 리스트 뽑기
    array = [False]*2 + [True]*n
    m = int(n**0.5)
    for i in range(2,m+1):
        if array[i] == True:
            for j in range(i*i,n,i):
                array[j] = False
    return array

primes = prime(1000000)

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())
    cnt = 0
    for i in range(N//2+1): # 대칭기준 같으면 제외
        if primes[i] and primes[N-i]:
            cnt += 1
    print(cnt)