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

import sys


def prime_num(num):
    sieve = [True]*num
    sieve[1] = False
    m = int(num**0.5) + 1

    for i in range(2, m):
        if sieve[i] == True:
            for j in range(i+i, num, i):
                sieve[j] = False

    return sieve



prime_list = prime_num(10001)
for t in range(int(input())):
    N = int(sys.stdin.readline())
    for number in range(N//2,0,-1):
        other_number = N - number
        if prime_list[other_number] and prime_list[number]:
            print(number,other_number)
            break

골드바흐의 추측 문제이다. 정수론에 관련된 문제로 소수를 구해서, 소수를 더해서 나오는 경우를 구하는데 그 중 두 소수의 차이가 작은 소수를 구하는 것이다.

 

구하는 방법은 다음과 같다. 먼저 나올 수 있는 경우가 1~10000이니깐, 1~10000 사이의 소수들을 전부 구해준다. 

그리고 난뒤 두 소수 차이가 가장 적은 경우를 구하는 경우이니깐 주어진 수 N의 절반인 N//2 부터 시작해서 0까지 반복을 하면서, 두 수가 전부 소수인 경우를 구해주면 된다.