[백준 9020] 골드바흐의 추측 python

문제

문제 요약 : 

모든 짝수를 두 소수의 합으로 나눌 수 있다는 골드바흐의 추측에 맞게 

주어진 짝수 n에 대하여 골드바흐 파티션을 출력하는 문제이다.

풀이

• 기본 아이디어 :
  • n을 반으로 나눈 다음 n에서 반으로 나눈 수와 가까운 소수를 뺐을 때 
  • 나머지가가 소수이면 골드바흐 파티션이 된 것 !
• 소수인지 판별
  • 에레토스테스테네스의 체 사용 ( 백준 1929 번 )
• 루프 사용
  1. 반복 변수 : tmp , n//2 부터 시작
  2. 반복 변수 갱신 :  0이 되기 전 까지 -1
  3. 종료 조건 : n- tmp 했을 때 소수가 나온다. 
• 반(n // 2) 만 체크하는 이유
  • 가장 차이가 적은 파티션을 찾아야 하니까.
  • 0부터 (n // 2)까지 반만 체크해도 n-tmp가 소수인지 체크하기 때문에 결국 0부터 n까지 전체가 다 체크되니까.

통과된 풀이

# 소수 구하기 - 에레토스테네스의 체
def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                return False
        return True

t = int(input()) # test case

for _ in range(t): 
    n = int(input())
    tmp = n // 2
    
    while tmp > 0:
        if isPrime(tmp):
            if isPrime(n - tmp):
                print(tmp, n-tmp)
                break
        tmp -= 1