[백준/9020/파이썬] 골드바흐의 추측

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

9020번: 골드바흐의 추측

Problem

• 골드바흐의 추측 , 오래전부터 알려진 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 개의 소수(Prime Number)의 합으로 나타낼 수 있다는 추측이다. 예를들어, 4 = 2+2 , 10 = 5+5 와같이 나타낼 수 있다는 추측이다.
• 이때, 2+2 와같이 2개의 수로 나타낸 것을 골드바흐 파티션이라고 한다. 10000보다 작거나 같은 모든 짝수 N에 대해서 골드바흐 파티션은 존재한다.
•  

조건

• 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.
• 4 ≤ n ≤ 10,000

 

 

SOL

G: 골드바흐 파티션을 가지는 짝수

G = A+B , A = PrimeNumber, B=PrimeNumber로 정의할 수 있다.

그러면, A,B가 소수인지 확인해야하고, 두 소수의 차이가 가장 작은 것을 출력하기 위한 고민을 해야한다.

 

소수인지/ 아닌지 판별

• A,B가 소수인지 확인하는 방법은 간단(?)하다. 아니, 소수인지 아닌지 판단하는 방법은 이미 Well-known (잘 알려져있다)이다.
• 완전 탐색 -> 반복 횟수 줄이기 -> 완전히 다른 방법으로 접근. 
• 이 3가지 방법이 대표적으로 있다. 이거에 대한 접근은 따로 글을 적는게 좋을것 같다. 

def Is_Prime(N):
    if N<2:
        return False
    for i in range(2,int(math.sqrt(N))+1):
        if N%i==0:
            return False
    return True

 

Trobule Shooting 

두 소수의 차이가 가장 작은 것을 출력하는 방법을 어떻게 구현할까

 

Idea 1

10000이하 오름차순으로 정렬된 소수 리스트를 갖고 , 앞에서부터 하나씩 반복하면 될지않을까 , 어차피 2개만 선택하면 되니까, n^2이면 해결될것같다.if arr[i] + arr[j] == G 를 만족하는  수 중에서, 변수에 sub=abs(arr[i]-arr[j])를 저장해놓고, 매번 차이를 갱신해서, 이전의 계산했던 sub보다 작다면, 새로 갱신 시켜줘야한다. 

 

단점) PrimeNumber의 길이^2만큼 반복을 해야하므로, TL의 위험성이 있다 . 좀 더 효율적으로 풀어보자.

 

Idea 2

숫자를 2개의 수의 합으로 쪼갤 때는 중간값부터 쪼개면 편하다.

예를들어, 12 = 6 + 6 , 5(6-1) + 7(6+1) , 4(6-2) + 8(6+2)...와 같이,6번의 반복으로 12를 2개의 합으로 나타낼 수 있게 된다. 이 골드바흐의 추측 문제는 이러한 과정에 이 두 숫자가 PrimeNumber인지 아닌지 판별하기만 하면 된다.

이렇게 되면, O(N/2)*O(logN), O(NlogN)으로 해결이 가능하다.

 

# 골드바흐의 추측
# 2보다 큰 모든 짝수는 두개의 소수(Prime Number)의 합으로 나타낼 수 있다.
# 10000보다 작거나 같은 모든 짝수 n에 대해서 골드바흐 파티션은 존재한다.

import sys
import math
input= sys.stdin.readline
tc=int(input().rstrip())
# 10000보다 작은 prime number를 구하면 되겟네. => Prime Number를 직접 구하면, 합을 구하는 과정에서 좀 번거롭다.

def Is_Prime(N):
    if N<2:
        return False
    for i in range(2,int(math.sqrt(N))+1):
        if N%i==0:
            return False
    return True 

while tc:
    target = int(input().rstrip())
    A= target//2
    B= target//2
    for i in range(target//2):
        if Is_Prime(A) and Is_Prime(B):
            print(A,B)
            break
        else:
            A-=1
            B+=1
    tc-=1