[백준] 17103번 : 골드바흐 파티션 (Python)

 

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

 

 

숫자 N의 골든바흐의 추측을 만족하는 소수의 개수를 구하는 문제다.

단, 두 소수의 순서만 다른 것은 같은 파티션이다.

 

import sys

input = sys.stdin.readline

# 에라토스테네스의 체로 소수 구하기
def prime(N):
    
    a = [False,False] + [True]*(N-1)
    primes=[]

    for i in range(2,N+1):
        
      if a[i]: # 소수이면
        primes.append(i)
        
        for j in range(2*i, N+1, i): # i의 합성수를 지움
            a[j] = False
    
    return primes, a

get_prime_numbers = 1000000
primes, all_primes = prime(get_prime_numbers) # 소수 구하기
T = int(input()) # 테스트 케이스의 수 T

for _ in range(T):
       
    golden_case = 0
    N = int(input()) # N
    
    # 골든바흐의 추측 검증
    for i in primes:  
        
        if(i > (N//2)): # N//2 이하의 소수들만
            break;
        
        # 골든바흐의 추측이 맞으면
        if(all_primes[N-i] and all_primes[i]):
            golden_case += 1
            
    print(golden_case)

 

 

 

[문제풀이]

---

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

 

백준 6588, 골든바흐의 추측 문제의 확장판이다.

소수 쌍을 구하면 되는데, 이 골든바흐의 추측을 만족하는 소수쌍은 좌우 대칭이다.

예)

N이 8일 때
소수 = [2, 3, 5, 7] <= 홀수 소수랬으니 2는 x

3 + 5 = 8 (검증 완료)
5 + 3 = 8 (검증 완료)

 

(3, 5), (5, 3)으로 대칭이다.

즉, N//2까지의 골든바흐의 추측을 만족하는 소수의 개수를 구하면 중복 소수쌍 없이 정답!