소스코드
import sys
input = sys.stdin.readline
T = int(input().strip())
MAX_N = 10000
# 1만까지 중에서 소수 찾기
sosu = [True] * (MAX_N+1)
sosu[0], sosu[1] = False, False
def find_sosu(sosu_arr):
for i in range(2, int(MAX_N**0.5) + 1):
if sosu_arr[i] == True:
for j in range(i*i, MAX_N+1, i):
sosu_arr[j] = False
find_sosu(sosu)
for _ in range(T):
n = int(input().strip())
for i in range(n // 2,0,-1):
if sosu[i] == True and sosu[n-i] == True:
sys.stdout.write(f"{n-i} {i}\n")
break
Python
복사
풀이
이 문제를 풀기 위해서는 다음 세 가지 부분을 파악해야합니다 :
# 1만까지 중에서 소수 찾기
sosu = [True] * (MAX_N+1)
sosu[0], sosu[1] = False, False
Python
복사
def find_sosu(sosu_arr):
for i in range(2, int(MAX_N**0.5) + 1):
if sosu_arr[i] == True:
for j in range(i*i, MAX_N+1, i):
sosu_arr[j] = False
Python
복사
for _ in range(T):
n = int(input().strip())
for i in range(n // 2,0,-1):
if sosu[i] == True and sosu[n-i] == True:
sys.stdout.write(f"{n-i} {i}\n")
break
Python
복사
•
우선 범위가 1만 이내 입니다. 최악의 경우 이중 반복을 통해 계산하더라도 (10^4 x 10^4 = 10^8)이므로 2초 제한 시간 안에는 가능합니다. 그러므로 소수라면 True로 설정할 배열을 생성합니다.
•
find_sosu 함수를 살펴보겠습니다. 첫번째로 나오는 반복문을 생각해봅시다. 1부터 1만까지 순회해야할까요? 그렇지 않습니다. 루트 1만까지만 살펴보면 됩니다. 소수는 자기 자신과 1을 제외한 약수가 없는 자연수입니다. 즉, 약수끼리 곱하면 자기 자신인건데 (루트1만 x 루트1만 = 1만)이니까 굳이 다 순회할 필요가 없겠죠?
◦
만약 해당 범위에서 True(소수) 값을 갖는 원소가 나오면 해당하는 인덱스의 배수는 모두 소수가 아닙니다. 그러므로 i씩 건너뛰면서 소수가 아님을 나타내는 False로 변경합니다.
•
이제 테스트 케이스 별로 순회하며 n에 대해서 결과를 출력할 차례입니다. n=8인 경우에 대해 골드바흐의 추측을 고려해보겠습니다.
◦
(1+7), (2+6), (3+5), (4+4), (5+3), (6+2), (7+1)
◦
잘 보면, 중간을 기점으로 숫자가 반복됩니다. 즉, 중간값 이하만 살펴보면 되겠죠.
◦
또한 가능한 상황이 여러 가지라면 두 소수의 차이가 가장 작아야합니다. 그러므로 역순으로 순회하는게 유리합니다.
◦
중간값 이하에서 역순으로 순회하면서 두 소수가 True(소수)라면, 값을 출력하고 다음 테스트 케이스로 넘어갑니다(break)