9020. 골드바흐의 추측

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

 

✔ 유형 : 수학

✔ 문제 풀이: 소수의 특성과 두 수의 합을 이용

 

골드바흐 추측

- 유명한 정수론의 미해결 문제

- 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.

 

문제 조건

- 입력받은 N은 2보다 큰 짝수이다.
- N은 두 소수의 덧셈 값으로 나타낼 수 있다.
- 여러 쌍이 있다면 두 소수의 차이가 가장 작아야한다.

 

 

N의 중간값을 기준으로 두고 a+b = N 일 때, a와 b의 차이를 벌리며 a,b 두 수가 소수인 지점을 찾는다.

 

 

 

def isPrime(a : int) -> bool :
    if ( a == 1 ) : False

    for i in range(2, 10001):
        if( i*i > a ) : break
        if( a%i == 0 ) : return False

    return True

pbCount = int(input())

for n in range(pbCount):
    N = int(input())
    a = N//2
    b = N//2

    while(True):
        if(isPrime(a) and isPrime(b)) :
            print(a,b)
            break

        a -= 1
        b += 1