[정글 알고리즘]-[중] 골드바흐의 추측

BEFORE for j in range(2, left): if left % j == 0: 소수 아님...

AFTER if prime[left] and prime[right]: → 즉시 확인

크래프톤 정글 / 정글에서 문제풀기 [정글 베이직] 골드바흐의 추측 백준 9020 · 수학, 소수 · Gold V 처음에 소수 판별을 매번 하려고 했다. 테스트케이스마다 for j in range(2, left)를 돌리면 되겠다고 생각했다. 논리는 맞는데, 뭔가 너무 많이 도는 것 같았다. 그때 에라토스테네스의 체를 처음 제대로 이해했다. 미리 계산해두면 조회가 O(1)이 된다는 것을 여기서 처음 느꼈다. · · · 문제 소개 4 이상의 짝수 n을 두 소수의 합으로 나타내되, 두 소수의 차이가 가장 작은 쌍을 출력하는 문제다.

항목	내용
입력	테스트케이스 수 T, 이후 T개의 짝수 n (4 ≤ n ≤ 10000)
출력	각 n에 대해 두 소수 a b (a ≤ b, 차이 최소)
핵심 도구	에라토스테네스의 체, n//2 대칭 탐색
난이도	Gold V

· · · 왜 n//2에서 시작하는가 n을 두 수의 합으로 쪼개면 항상 n//2를 기준으로 대칭이다.

n = 26 일 때 가능한 조합:

 3 + 23  →  차이 20
 5 + 21  →  차이 16
 7 + 19  →  차이 12
11 + 15  →  차이  4
13 + 13  →  차이  0  ← 가장 작음

n//2 = 13 에서 시작하면 차이가 최소인 쌍부터 확인한다.

핵심
가운데에서 시작 → 바깥으로 이동 → 처음 발견한 두 소수 쌍이 곧 차이 최솟값

n = 28 탐색 흐름

left -= 1 / right += 1 하면서 소수 쌍 탐색

14 + 14

✗ 둘 다 소수 아님

13 + 15

✗ 15는 소수 아님

12 + 16

✗ 둘 다 소수 아님

11 + 17

✓ 둘 다 소수 → 출력

· · · 에라토스테네스의 체 0~10000까지 소수 여부를 배열로 미리 저장한다. 이후 조회는 prime[x] 한 번으로 끝난다. ① 초기 상태 — 전부 True로 가정

prime = [True] * 10001 → prime[0] = prime[1] = False

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

② i = 2 — 2의 배수 제거

range(4, 10001, 2) → 4, 6, 8, 10, 12 ...를 False로

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

③ i = 3 — 3의 배수 제거 (i*i = 9 부터)

range(9, 10001, 3) → 9, 12, 15 ...를 False로 (6은 이미 제거됨)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

④ 최종 — 소수만 남음

초록 = 소수 / 어두운 빨강 = 합성수

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

· · · range(i*i, 10001, i) 해부 이 한 줄이 배수 제거의 전부다. 세 인자가 각각 무엇을 뜻하는지 분리해서 보자.

i*i 시작점

,

10001 끝 (10000 포함)

,

i ← 이게 배수를 만든다

# i = 2 range(4, 10001, 2) → 4 6 8 10 12 ... (2씩 증가 = 2의 배수) # i = 3 range(9, 10001, 3) → 9 12 15 18 ... (3씩 증가 = 3의 배수) # i = 5 range(25, 10001, 5) → 25 30 35 ... (5씩 증가 = 5의 배수)

왜 i*i부터 시작하는가
i = 5라면 5×2=10, 5×3=15, 5×4=20은 이미 2와 3의 배수로 제거됐다.
처음으로 새로 제거되는 수는 5×5=25. 그래서 i*i부터 시작한다.

단계별 요약

i = 2 range(4, 10001, 2) 4, 6, 8, 10, 12 ... 2씩 증가 → 2의 배수

i = 3 range(9, 10001, 3) 9, 12, 15, 18 ... 6은 이미 제거됨

i = 5 range(25, 10001, 5) 25, 30, 35, 40 ... 10/15/20 이미 제거

· · · 풀이 흐름

1

소수 배열 미리 생성 prime = [True] * 10001 후 에라토스테네스 체 실행

2

테스트케이스 반복 t = int(input()) → for _ in range(t):

3

가운데에서 시작 left = right = n // 2

4

소수 쌍 탐색 (while) 둘 다 소수면 출력 후 break, 아니면 left -= 1 / right += 1

· · · 최종 코드

# 수학 - 골드바흐의 추측 (백준 9020)
# https://www.acmicpc.net/problem/9020

# ── 1단계: 에라토스테네스의 체 ──────────────
prime = [True] * 10001
prime[0] = prime[1] = False

for i in range(2, 101):          # √10000 = 100
    if prime[i]:
        for j in range(i*i, 10001, i):  # i의 배수 제거
            prime[j] = False

# ── 2단계: 골드바흐 파티션 탐색 ─────────────
t = int(input())

for _ in range(t):
    n = int(input())
    left  = n // 2
    right = n // 2

    while True:
        if prime[left] and prime[right]:
            print(left, right)
            break
        left  -= 1
        right += 1

· · · 예제 검증

# 입력
3
8
10
16

# n = 8  →  left=4, right=4  →  4소수X  →  3+5  ✓
# n = 10 →  left=5, right=5  →  5+5  ✓
# n = 16 →  left=8, right=8  →  X  →  7+9 X  →  ... →  5+11  ✓

# 출력
3 5
5 5
5 11

· · · 복잡도

단계	복잡도	이유
에라토스테네스 체	O(n log log n)	n = 10000, 사실상 상수
각 테스트 탐색	O(n)	최대 n//2 번 이동
전체	O(n log log n + T·n)	T=1000, n=10000 → 충분히 빠름

핵심 비교
매번 소수 판별: 테스트케이스마다 O(√n) × 탐색 횟수
에라토스테네스 체: 딱 한 번 O(n log log n), 이후 조회 O(1)
반복 계산은 미리 계산으로 바꾼다 — 이게 이 문제의 핵심이다.

· · ·

이번 문제에서 가져가는 것

• 소수 문제가 나오면 에라토스테네스의 체 먼저 떠올린다. 매번 판별하는 건 느리다.
• range(시작, 끝, 간격)에서 간격이 핵심이다. 간격 i가 i의 배수를 만들어낸다.
• i*i부터 시작하는 이유를 이해했다. 그보다 작은 배수는 이미 더 작은 소수에서 제거됐다.
• n//2에서 시작하면 차이가 가장 작은 쌍부터 탐색된다. 대칭 구조를 이용한 것.