[Silver II] 골드바흐 파티션 - 17103

문제 링크

성능 요약

메모리: 48872 KB, 시간: 2636 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2023년 12월 20일 19:01:03

문제 설명

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

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

import math
import sys
input = sys.stdin.readline

t = int(input())
arr = [False, False] + [True] * (999999)
for i in range(2, int(math.sqrt(1000000))+1):
    if arr[i]:
        for j in range(2*i, 1000001, i):
            arr[j] = False

for _ in range(t):
    n = int(input())

    count = 0
    for i in range(2, n//2+1):
        if arr[i] and arr[n-i]:
            count += 1
    print(count)

풀이

처음에 입력 데이터까지의 소수들을 찾아 이를 반복하여 합이 입력 데이터와 같으면 결과를 출력하도록 했는데 순서가 다른 소수는 같은 파티션으로 구분하는 것을 어떻게 해야할지 고민하다 구글링을 해봤다.

import math
import sys
input = sys.stdin.readline

def prime(x):
    arr = [False, False] + [True] * (x-1)
    for i in range(2, int(math.sqrt(x))+1):
        if arr[i]:
            for j in range(2*i, x+1, i):
                arr[j] = False
    sosu = []
    for i in range(len(arr)):
        if arr[i]:
            sosu.append(i)
    return sosu


t = int(input())
for _ in range(t):
    n = int(input())
    arr = prime(n)
    count = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if arr[i] + arr[j] == n:
                count += 1
    print(count)

구글링을 하니 소수를 따로 저장하지 않고 그냥 소수 판별을 한 상태에서 두 수가 소수인지 확인하는 방식으로 갔다.

이렇게 하여 출력이 정확하게 나왔는데 시간초과가 나와서 어떻게 해야하지 하다 입력 데이터의 조건으로 2이상 1000000이하였기 때문에 1000000까지의 소수를 모두 구하고 입력 데이터까지의 수만큼을 확인하는 것으로 했다.