[Coding test][실버I]BOJ #9020 골드바흐의 추측(수학, 정수론, 소수 판정, 에라토스테네스의 체)

내 풀이

def prime_list(a):
    sieve = [True] * (a+1)

    checkrange = int((a+1)**0.5)

    for i in range(2,checkrange+1):
        if sieve[i] == True:
            for j in range(i+i,a+1,i):
                sieve[j] = False

    sieve[0] = False
    sieve[1] = False

    return sieve

lst_sieve = prime_list(10000)


import sys

t = int(sys.stdin.readline().rstrip())

for i in range(t):
    n = int(sys.stdin.readline().rstrip())

    for sieve_index_num in range(int(n/2),0,-1):  #에라토스테네스의 체에서 입력받은 n의 중간값부터 역순으로 접근.
        if lst_sieve[sieve_index_num] == True: #만약 현재 체의 인덱스값이 소수라면
            if lst_sieve[n-sieve_index_num] == True: #만약 n-체의 인덱스값도 소수라면
                print(sieve_index_num, n-sieve_index_num) #순서대로 출력하고 안쪽 for문탈출, 다음값 입력받음
                break
            else:
                continue #다음 sieve_index_num으로 넘어감(-1)

문제 정의

문제 분석

# 여러가지 경우가 가능한 경우를 막기위해, 중간값에서 먼쪽으로 나아간다. 
# 가장먼저 발견되는 경우가 두 소수의 차이가 가장 작은 것이다.

#1. 입력받은 짝수n를 2로 나누어  n/2 부터 탐색을 시작한다.
#2. n/2 이하의 수들 중, 소수x를 발견하면-> n-x도 소수라면->출력

에라토스테네스의 체를 활용한 문제이다. 에라토스테네스의 체, 백준1929번

입력이 4부터 10000이므로, 에라토스테네스의 체를 활용해 4부터 10000까지의 소수를 구한 리스트를 만들고
필요한 값을 리스트에서 검색해 사용하면 시간을 대폭 감소시킬 수 있다.
테스트 케이스별로 골드바흐 파티션을 찾을 경우, n이 커지고 테스트 케이스가 많아질수록 시간이 오래 걸릴 것이기 때문이다.

주의점

1. 입력은 4이상 10000이하. (에라토스테네스의 체를 이용해 미리 구한다.)
2. 입력은 모든 짝수이다.
3. 입력으로 들어오는 모든 짝수에 골드바흐파티션이 존재한다.
4. 여러가지일 경우, 두 소수의 차이가 가장 작은 것 출력
5. 출력하는 소수는 작은 것 부터

골드바흐 파티션이 여러가지인 경우

주의점의 4,5번을 보자.
입력으로 8이 들어온다면

(1+7) = 8
(3+5) = 8
(5+3) = 8
(7+1) = 8

로 2개의 골드바흐 파티션을 가진다는 것을 알 수 있다.(중복제외)

1부터 모든 골드바흐 파티션을 찾을수도 있지만, 반대로 생각하면
차이가 작은 것부터 찾으면 1개만 찾으면 된다.

다른 예시를 보자.

(3+13) = 16
(5+11) = 16
(11+5) = 16
(13+3) = 16


(1+19) = 20
(3+17) = 20
(7+13) = 20
(13+7) = 20
(17+3) = 20
(19+1) = 20

규칙성을 찾겠는가?

n의 골드바흐 파티션을 이루는 두 수 중 작은 수는 2/n을 넘을 수 없다!

라는 것이다.

2개의 소수를 더해 n을 만들어야하기때문에, 2/n 이상에서는 중복되는 파티션이 나온다.
마치 소수판정할때, n**0.5이하의 수로 판정하는 것과 비슷한 이치이다.

따라서, n이 주어지면, 에라토스테네스의 체 안에서 n/2 부터 0까지 -1씩 인덱스값을 줄여나가며
맨 처음 발견되는 골드바흐 파티션 중 두 소수의 차이가 가장 작은 것이다.