백준 파이썬 17103번 골드바흐 파티션 (Today I Learn 2024.04.20)

20240420 백준 파이썬 공부
17103번 골드바흐 파티션

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

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

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

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

>>>코드1. 시간 초과 >> 매 입력때마다 소수인 것인지 확인하고, 체크하니 시간초과가 걸림

import math

def primenum(n):
    c = True
    for i in range(2, int(math.sqrt(n))+1):
        if n%i == 0:
            c = False
            break
    return c

for _ in range(int(input())):
    n = int(input())
    count = 0
    for i in range(2, n//2+1):
        if primenum(i) == True:
            if primenum(n-i) == True:
                count += 1
    print(count)

>>>코드2. 미리 최대 수 이하의 소수를 집합에 저장, 해당 수가 소수 집합에 포함되는지 검사

import math
# 소수인지 검사하는 코드
def primenum(n):
    c = True
    # 2 부터 n의 제곱근까지 검사시 나누어 지는 것이 없다면 소수
    for j in range(2, int(math.sqrt(n))+1): 
        if n%j == 0:
            c = False
            break
    return c
# 소수 집합 생성
prime = set()
# 최대 n인 1000000까지의 소수를 저장한 집합 만들기
for i in range(2, 1000001):
    if primenum(i) == True:
        prime.add(i)
# 골드바흐 파티션 검사
for _ in range(int(input())):
    n = int(input())
    count = 0
    for i in range(2, n//2+1):
        if i in prime and n-i in prime:
            count += 1
    print(count)

>>>문제링크
https://www.acmicpc.net/problem/17103