[파이썬] 9020번: 골드바흐의 추측

 

9020번: 골드바흐의 추측

소수: 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수

 

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

이러한 수를 골드바흐 수라고 함. 

두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 함.

 

10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재함.

 

2보다 큰 짝수 n이 주어졌을 때 n의 골드바흐 파티션을 출력하는 프로그램 작성

만약 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력.

 

 

소수 판별 함수 정의 -> 문제에 정의된 범위 내에서 소수만 따로 골라냄 -> prime이라는 리스트에 저장

이렇게 해두고 n을 입력받은 후에 prime 리스트의 원소를 어떻게 해서 결과를 구해보려고 했는데 머리가 도저히 돌아가지를 않아서 결국엔 구글링했다.

 

참고링크: [백준] 9020 골드바흐의 추측(실버1) - Python (velog.io)

# 소수 판별 함수
def sosu(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5 + 1)):
        if n % i == 0:
            return False
    return True


for _ in range(int(input())):  # 테스트케이스를 이렇게 입력받을 수도 있음!
    n = int(input())

    a, b = n // 2, n // 2  # 입력받은 n을 반으로 쪼개 각각 a, b에 저장
    while a > 0:
        if sosu(a) and sosu(b):  # a와 b 둘 다 소수일 경우에 출력
            print(a, b)
            break  # break문을 안 넣었더니 반복문이 무한으로 출력되었음
        else:
            a -= 1  # 문제에서 작은 소수부터 출력하라고 했으므로 a는 1을 빼고, b는 1을 더한다.
            b += 1

소수를 따로 리스트에 저장해둘 필요가 없었다!

n을 반으로 쪼개서 a와 b에 나누어 저장한 후 각각이 소수인지 판별하면 더 간단하다.

 

항상 테스트케이스 입력받을 때 맨 윗줄에 t = int(input())을 입력했었는데 range 자체에 int(input())을 지정해줄 수 있다는 것도 배웠다.