[BOJ]#9020-골드바흐의 추측

9020번 골드바흐의 추측

골드바흐의 추측(Goldbach's conjecture)을 기반으로, 주어진 짝수를 두 개의 소수 합으로 나타내는 문제이다.

(대충 문제와 요구사항)
.
.
.
.
.
.

문제풀이 순서 📝

1️⃣ 에라토스테네스의 체로 소수 판별

• 결국에는 소수의 합들을 구하는 것이기 때문에 빠른 동작을 위해 소수 판별 알고리즘을 만든다.

2️⃣ 테스트 케이스 개수 입력 받기

• 몇 번의 테스트 케이스를 받을 것 인지 입력받는다.

3️⃣ 입력받은 짝수를 두 소수의 합으로 표현

• 입력받은 짝수 num을 두 개의 소수의 합으로 분해.

⚠️ 코드 스포 주의 ⚠️

.
.
.
.
.
.
.

전체 코드 🖥️

import sys

input = sys.stdin.readline

prime = [True] * (10001)

for i in range(2, 10001):
    if prime[i]:
        n = i * 2
        while n <= 10000:
            prime[n] = False
            n += i
            
t = int(input())

for _ in range(t):
    num = int(input())
    
    
    for i in range(num // 2, 1, -1):  
        if prime[i] and prime[num - i]:
            print(i, num - i)
            break 

.
.
.
.

코드 풀이 👨‍💻

1️⃣ 에라토스테네스의 체로 소수 판별

prime = [True] * (10001)

for i in range(2, 10001):  # 2부터 10000까지 탐색
    if prime[i]:  # i가 소수라면
        n = i * 2  # i의 배수들을 False로 변경하기 시작
        while n <= 10000:
            prime[n] = False  # i의 배수는 소수가 아님
            n += i  # i의 배수 탐색

prime[i]가 True이면 i가 소수임을 의미.
10001 크기의 리스트를 모두 True로 초기화.

• 에라토스테네스의 체 알고리즘
  - i가 소수이면 i의 배수들은 모두 소수가 아님.
  - n = i * 2 부터 10000 이하의 배수를 False로 변경.
  - 결과적으로 prime[i]가 True이면 i는 소수이고, False이면 합성수이다.

2️⃣ 테스트 케이스 개수 입력 받기

t = int(input())			# 테스트 케이스 횟수 입력 받기

3️⃣ 입력받은 짝수를 두 소수의 합으로 표현

for _ in range(t):  # 테스트 케이스 개수만큼 반복
    num = int(input())  # 짝수 입력받기
    
    for i in range(num // 2, 1, -1):  # 중앙에서 시작하여 감소 탐색
        if prime[i] and prime[num - i]:  # 두 숫자가 모두 소수라면
            print(i, num - i)  # 가장 가까운 두 소수를 출력
            break  # 첫 번째로 찾은 값이 가장 차이가 적으므로 즉시 종료

• 입력받은 짝수 num을 두 개의 소수의 합으로 분해.

• for i in range(num // 2, 1, -1):
  - num // 2에서 시작하여 가장 차이가 적은 두 소수를 찾음.
  - i가 감소하면서 탐색하므로 가장 가까운 소수 쌍을 찾는 즉시 종료 가능.

• if prime[i] and prime[num - i]:
  - 두 수가 모두 소수인지 확인.
  - 처음으로 발견된 (i, num - i)가 최적해이므로 break로 루프 종료.