1. 골드바흐의 추측

골드바흐의 추측(Goldbach's conjecture)은
오래전부터 알려진 정수론의 미해결 문제로,
2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것이다.
이때 하나의 소수를 두 번 사용하는 것은 허용한다.

출처 : 위키백과 - 골드바흐의 추측

골드바흐 파티션

짝수를 두 소수의 합으로 나타내는 표현을
그 수의 골드바흐 파티션이라고 한다. 예를 들면 아래와 같다.

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5
12 = 5 + 7
14 = 3 + 11
14 = 7 + 7

이 있다.

출처 : BOJ_9020 골드바흐의 추측

소수 판별법

입력받은 수가 소수인가?

소수 = 1과 자기 자신만을 약수로 갖는 수 이므로
1과 자기 자신 이외의 수로 나누어 떨어진다면 소수가 아니다.

따라서, 다음과 같은 함수로 판별할 수 있다.

def is_prime_number(num):
	if num <= 1:
    	return False
        
	for i in range(1, num):
    	if num % i == 0:
        	return False
	return True

여기서 약수의 성질을 조금만 더 생각해보면
다음과 같은 특징을 알 수 있다.

24의 약수를 나열해보자.
1 2 3 4 6 8 12 24

24 / 2 = 12
24 / 3 = 8
24 / 4 = 6

어떤 수를 그 수의 약수로 나눈 몫 또한 그 수의 약수임을 알 수 있다.

따라서, 다음과 같은 대칭성을 갖게된다.
1 2 3 4 ←→ 6 8 12 24

입력받은 어떤 수가 제곱수라면, 약수의 개수는 홀수이다.

36의 약수
1 2 3 4 ←6→ 9 12 18 36

따라서 입력받은 수(num)가 소수인지 판단하기 위해서
2부터 $\surd$num 이하의 수로 나누어 떨어지는지만 확인해 주어도 판단할 수 있다.

def is_prime_number(num):
	if num <= 1:
	    return False

	i = 2
    while i * i <= num:
    	if num % i == 0:
        	return False
		i += 1
	return True

한번에 많은 수를 판별해야 할 경우

에라토스테네스의 체를 이용한다.

소수는 1과 자기 자신만을 약수로 갖기 때문에
소수 자신을 제외한 소수의 배수는 소수가 아니다.

따라서, 입력되는 수 중 가장 큰 수 만큼의 길이를 가지는 bool type 배열을 선언한 뒤
인덱스가 소수일 경우True를, 아닐 경우 False를 저장하는 방식으로
범위 내의 소수들을 판단하는 배열을 만들 수 있다.

n = 10001 #	1~10000 범위의 소수를 판별
is_prime_number = [True for _ in range(n)]

# 2의 배수부터 확인
for i in range(2, n):
	# i*2(가장 작은 소수) 부터 n까지 i씩 증가시킴
    # 따라서, j는 i의 (i를 제외한)배수가 됨
	for j in range(i*2, n, i):
        # 1보다 큰 자연수의 자신을 제외한 배수는 소수가 될 수 없으므로, False 저장
    	is_prime_number[j] = False

문제 풀이

BOJ 골드바흐의 추측

테스트 케이스 갯수만큼 입력된 수에 대한 골드바흐 파티션을 출력하는 문제이다.

먼저, 테스트 케이스만큼의 입력이 들어오기 때문에
입력으로 들어온 여러개의 소수를 판단해야하는 문제이고,
n의 범위가 10000 이하이므로
충분히 배열로 만들어서 판별 할 수 있다.

따라서 소수 판별을 위한 배열을 먼저 초기화 한다.

n = 10001
is_prime_number = [True for _ in range(n)]

for i in range(2, n):
	for j in range(i*2, n, i):
    	is_prime_number[j] = False

그 다음, 입력받은 수의 골드바흐 파티션을 출력해 주는데

먼저 입력받은 수 num의 골드바흐 파티션을 확인하기 위해서는

num = a + b 일 때, b = num - a 이므로

a가 소수이고 num-a 도 소수라면

a 와 b 는 골드바흐 파티션이다.

이때 출력 조건으로 '소수는 작은 수 부터 출력 한다'고 주어져 있다.

따라서 num / 2 부터 시작하여 감소하는 방향으로 구현하였다.

[ 전체 코드 ]

import sys

# 입력 최대값
max_num = 10001

# 소수 판별 배열 선언 및 초기화
p_num = [True for _ in range(max_num)]
p_num[0] = False
p_num[1] = False

for i in range(2, max_num):
    if p_num[i] is True:
        for j in range(i*2, max_num, i):
            p_num[j] = False

# 입력 시작
tc = int(sys.stdin.readline().rstrip())
for _ in range(tc):
    n = int(sys.stdin.readline())
    # n//2부터 2까지 1씩 감소한다.
    for i in range(n//2, 1, -1):
        if p_num[i] and p_num[n-i]:
        	# 찾았으면 출력 후 반복문 종료
            sys.stdout.write(f'{i} {n-i}\n')
            break