백준 / 실버 2 / 9020. 골드바흐의 추측

• 많은 양의 숫자를 하나하나씩 소수인지 아닌지 매번 확인해야 하는 문제
• 아래와 같은 알고리즘으로, 숫자의 소수 여부를 확인할 수 있음

def check_prime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

• 하지만 $O(\sqrt{N})$의 시간 복잡도... 조금 더 빠르게 소수 여부를 확인할 순 없을까?

에라토스테네스의 체

• 주어진 범위 내의 모든 소수를 효율적으로 구하는 알고리즘
• 처음엔 모든 수가 소수라고 가정하고, 소수가 아닌 수를 하나씩 없애는 방식

절차

• (1) $2$부터 $n$까지 자연수 나열
• (2) 남은 숫자 중 가장 작은 자연수 $p$를 선택한 뒤, $p$ 자신을 제외한 $p$의 배수를 모두 지움
• (3) $p \leq \sqrt{n}$까지 (2)를 반복
• (4) 남은 수는 모두 소수

# 에라토스테네스의 체
# 2부터 N까지 숫자 나열
is_prime = [True] * (n + 1)     # 소수인 경우 True, 아니면 False를 담은 배열
is_prime[1] = False             # 1은 소수가 아님

# sqrt(N)까지 아래 과정을 반복
for i in range(2, int(math.sqrt(n)) + 1):
    # 남은 숫자 중 가장 작은 숫자 -> i
    if is_prime[i]:
        # i의 배수를 모두 지움 (i * i 이전의 배수는 이미 지워졌음에 유의)
        for j in range(i * i, n + 1, i):
            is_prime[j] = False

• (2) 왜 $p$의 배수 중 $p \times p$부터 확인하나요?
  • $p \times (p-1)$까지의 배수는 앞에서 이미 지웠기 때문
  • e.g., $p=3$일 때 $6 = 3 \times 2$는 2의 배수 지울 때 이미 지워짐

• (3) 왜 $p \leq \sqrt{n}$까지만 구해도 되나요?
  • $p > \sqrt{n}$일때 $p$의 모든 배수는 앞에서 이미 지웠기 때문
  • e.g., $n=20$일 때 $\sqrt{n} = 4.\text{xx}$
    • 이때 $4$보다 더 큰 $5$의 배수 $10$, $20$($2$의 배수), $15$($3$의 배수)는 이미 앞에서 지움

시간 복잡도

• $2$부터 $N$까지 중 소수를 구할 떄
  • $2$의 배수 -> 약 $\frac{N}{2}$개의 수를 지움
  • $3$의 배수 -> 약 $\frac{N}{3}$개의 수를 지움
  • $5$의 배수 -> 약 $\frac{N}{5}$개의 수를 지움
  • 이를 다 더하면 $N(\displaystyle\sum_{i는 소수}\frac{1}{i})$개의 수를 지움
  • $(\displaystyle\sum_{i는 소수}\frac{1}{i})$는 수학적으로 $\log \log N$으로 근사됨
• 체를 만들 때 $O(N \log \log N)$
• 배열 접근은 $O(1)$이므로, 체를 한 번 만들어 두면 빠르게 소수 여부 판별 가능

풀이 및 시간 복잡도

• 에라토스테네스의 체를 사용하지 않은 풀이

import math

def check_prime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

T = int(input())

for _ in range(T):
    n = int(input())
    for i in range(n // 2, 0, -1):
        if check_prime(i) and check_prime(n - i):
            print(i, n - i)
            break

• 시간 복잡도
  • 최대 ${N}$번, $O(\sqrt{N})$의 시간 복잡도를 갖는 check_prime 함수 실행
  • 위 연산을 $T$회 반복
  • 최종 $O(T \times N\sqrt{N})$

• 에라토스테네스의 체를 사용한 풀이

import math

T = int(input())
nums = []

for _ in range(T):
    nums.append(int(input()))
max_n = max(nums)

# 에라토스테네스의 체
# 2부터 N까지 숫자 나열
is_prime = [True] * (max_n + 1)     # 소수인 경우 True, 아니면 False
is_prime[1] = False                 # 1은 소수가 아님

# sqrt(N)까지 아래 과정을 반복
for i in range(2, int(math.sqrt(max_n)) + 1):
    # 남은 숫자 중 가장 작은 숫자 -> i
    if is_prime[i]:
        # i의 배수를 모두 지움 (i * i 이전의 배수는 이미 지워졌음에 유의)
        for j in range(i * i, max_n + 1, i):
            is_prime[j] = False

for n in nums:
    for i in range(n // 2, 0, -1):
        if is_prime[i] and is_prime[n - i]:
            print(i, n - i)
            break

• 시간 복잡도
• 이때 에라토스테네스의 체는 딱 1번만 만들고, 모든 테스트 케이스에서 사용된다는 점에 유의할 것
  • $T$번의 테스트 케이스를 입력받으며, 체를 만들 때 필요한 최댓값을 구함: $O(T)$
  • 에라토스테네스의 체를 만듦: $O(N \log \log N)$
  • $T$번의 테스트 케이스에 대해 최대 ${N}$번, is_prime 배열에서 소수 여부를 확인: $O(T \times N)$
  • 최종 $O(T \times N + N \log \log N)$

실제 소요 시간 비교

• 맨 밑에 412ms 걸린 풀이가 에라토스테네스의 체를 사용하지 않은 풀이
• 위에 168ms 걸린 풀이가 에라토스테네스의 체를 사용한 풀이
• 시간제한이 2초라 두 풀이 다 정답으로 인정됐지만, 암튼 약 3배 빠르다는 점을 알 수 있음