백준 python 문제 - 골드바흐의 추측(9020)

백준 문제 - 골드바흐의 추츨(9020)

 

[문제 간단 설명]

2보다 큰 짝수 n이 주어졌을 때, 두 개의 소수로 합을 나타낼 수 있는 프로그램을 만들어라.

 

[문제 풀이 핵심]

1. 2보다 큰 짝수 n은 짝수이다.

2. 문제에서 방법이 여러가지가 있다고 하더라도 두 숫자의 차가 최소가 되는 방법을 사용하라고 명시하였다.

3. 숫자의 범위는 4부터 10,000까지이다.

 

[문제 풀이 과정]

1. 에라토스테네스의 체의 원리를 이용한다. 에라토스테네스의 체란 2부터 시작해서 각각 숫자의 배수를 지워나가는 과정을 의미힌다. 이 과정을 사용하면 하나하나 숫자를 확인하는 것보다 작동 시간을 획기적으로 줄일 수 있다.

 

[소스 코드]

import sys

T = int(sys.stdin.readline())

demicial_list = [False, False] + [True]*9999
a = int((10001**0.5)+1)
for i in range(1, a):
    if demicial_list[i] == True:
        for j in range(2*i, 10001, i):
            demicial_list[j] = False

for i in range(T):
    n = int(sys.stdin.readline())
    a = n // 2
    b = n // 2
    while True:
        if demicial_list[a] == True and demicial_list[b] == True:
            print(a, b)
            break
        else:
            a -= 1
            b += 1

 

[작동 원리]

1. 에라토스테네스의 체의 원리를 이용한 소수 리스트를 미리 만든다. 여기서 수의 범위가 주어졌기에, 거기에 해당하는 분량만 제작한다.

2. 테스트 횟수 만큼 반복하도록 for문을 작성한다.

3. n은 짝수이므로 시작은 절반으로 시작한다. 그리고 각자 +-1을 하여 두 숫자의 차이를 하나씩 넓혀가며, if문을 이용해 두 숫자가 소수 리스트에 해당하는 경우에 그 숫자를 뽑아내도록 만든다.