백준 6588번 문제풀이 : 소수 판별 알고리즘

1. 문제 분석

✅ 문제 한 문장 요약

4보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 골드바흐의 추측을 검증하는 문제

✅ 조건

• 입력: 짝수 n (4 ≤ n ≤ 1,000,000)
• 출력: n = a + b (두 홀수 소수 a, b 찾기)
• 조건: 두 개의 소수 합으로 표현해야 함

---

2. 의사 코드

1. 에라토스테네스의 체를 사용하여 1,000,000 이하의 모든 소수를 미리 계산한다.
2. 입력된 짝수 n에 대해:
   • 3부터 n//2까지 반복하며 두 개의 소수 (a, b)를 찾는다. (한 수가 다른 한 수보다 클 수 없음 → n//2까지만 탐색)
   • a + b = n이 성립하면 출력 후 종료.
3. 만약 두 개의 소수로 표현할 수 없다면 "Goldbach's conjecture is wrong." 출력.

---

3. 코드

import sys

# 1️⃣ 에라토스테네스의 체로 소수 판별 배열 생성
MAX = 1000000
is_prime = [True] * (MAX + 1)
is_prime[0], is_prime[1] = False, False  # 0과 1은 소수가 아님

for i in range(2, int(MAX ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, MAX + 1, i):
            is_prime[j] = False

# 2️⃣ 입력 처리
input = sys.stdin.read
data = map(int, input().split())

# 3️⃣ 짝수 n을 두 소수의 합으로 표현
for n in data:
    if n == 0:
        break

    found = False
    for a in range(3, n // 2 + 1, 2):  # 3부터 n//2까지 홀수 소수 탐색
        b = n - a
        if is_prime[a] and is_prime[b]:  # 두 수가 모두 소수인지 확인
            print(f"{n} = {a} + {b}")
            found = True
            break

    if not found:
        print("Goldbach's conjecture is wrong.")

---

4. 최적화 검토

• sys.stdin.read() 사용하여 여러 개 입력을 빠르게 처리