백준 골드바흐의 추측

2023.01.03 복습 => 실패

 

이 문제는 결국 구글링의 도움을 얻었던 문제이다.

10000까지의 소수를 모두 구하여 리스트에 담는 것 까지는 쉽게 했다.

하지만, 입력 받은 숫자가 두 소수의 합이 되게끔하는 두 수를 찾는 방법을 생각해내기가 어려웠다.

두 수를 소수 리스트에서 꺼낼 생각만 하고 있었는데, 구글링을 해보니 굳이 두 숫자를 찾을 필요가 없었다.

하나의 소수를 픽한다면, 나머지 하나는 당연히 입력 받은 숫자에서 픽한 소수가 되는 것이다..

결국엔 소수를 하나 정한 뒤, 입력받은 숫자에서 픽한 소수를 뺀 숫자가 소수인지 아닌지 확인해서 출력하는 문제..

두 소수의 차이가 가장 적은 것을 출력하라고 했으니 입력받은 숫자를 반으로 나눠 하나씩 줄여가면서 보면 된다.

코드도 매우 간결하다.

def sosu(x):  # 소수를 판별해주는 함수
    for i in range(2,x):
        if x%i==0:
            return 0
    return 1

num=[] 	#소수를 담을 리스트
for i in range(10000):
    if sosu(i)==1:
        num.append(i)

t=int(input())
for i in range(t):
    n=int(input())
    for a in range(n//2, 1, -1):  # 절반부터 2까지 하나씩 줄여가면서 탐색
        if a in num and n-a in num:  # 만약 a와 입력받은 숫자-a가 소수라면
            print(a, n-a)
            break