백준 9020 풀이

9020

골드바흐의 추측

문제의 최초 접근 : 2 ~ n까지의 소수 구하기 , 구한 소수 중 차이가 가장 작은 값 찾기

I P O

I : 프로그램 실행 횟수 , 골드바흐의 추축을 진행할 수 (프로그램 실행 횟수 만큼 줄바꿈 구분을 통해)

P : 2 ~ 입력받은 수 까지의 소수, 입력받은 수의 골드바흐 파티션 구하기

O : 입력받은 수 별로 골드바흐 파티션 (프로그램 실행 횟수 만큼 줄바꿈 구분을 통해)

source code

• 2 ~ n까지의 숫자를 리스트에 담고 제곱근을 활용해 소수 구분. 만약 2~제곱근 까지의 나눗셈을 진행시 나머지가 0인경우 리스트에서 삭제

if n[j] % 2 == 0:
    handler = int(math.sqrt(n[j]))

    for k in range (2,n[j]+1):
        handler = int(math.sqrt(k))

        for i in range (2 , handler + 1 ):
            if k % i == 0:
                num_list.remove(k)
                break
print(num_list)

• 현재 골드바흐의 추측을 실행하는 수 - 소수의 값이 소수만 담아놓은 리스트에 있는지 확인 후 , 있으면 새로운 리스트에 추가 추가된 값들 중 차이가 가장 작은 값 출력(리스트의 가운데 있는 값)

  for num in num_list:
    handler = n[j] - num
    #print("----\n" , n[j] , handler , num)
  
    if handler in num_list:
        a = [num , handler]
        result_list.append(a)
  print(result_list[(len(result_list)//2)][0],result_list[(len(result_list)//2)][1])
  

final source code

"""
골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 
두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 
또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 
예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 
14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 
골드바흐 파티션은 존재한다.

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

import math 
n = []
T = eval(input())
for num in range (T):
    n.append(eval(input()))

result_list = []

for j in range (T):
    num_list = []
    result_list = []
    a = []
    if n[j] >= 4 and n[j] <= 10000:
        num_list = list(range(2,n[j] + 1))

        if n[j] % 2 == 0:
            handler = int(math.sqrt(n[j]))

            for k in range (2,n[j]+1):
                handler = int(math.sqrt(k))

                for i in range (2 , handler + 1 ):
                    if k % i == 0:
                        num_list.remove(k)
                        break
            #print(num_list)

            for num in num_list:
                handler = n[j] - num
                #print("----\n" , n[j] , handler , num)

                if handler in num_list:
                    a = [num , handler]
                    result_list.append(a)
            print(result_list[(len(result_list)//2)][0],result_list[(len(result_list)//2)][1])