[Python | 4948] 베르트랑 공준

https://www.acmicpc.net/problem/4948

---

문제 설명

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

 

📌 시간 제한: 1초

---

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

---

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

---

문제 접근

베르트랑 공준은 임의의 자연수 \(n\)에 대해 \(n < x \leq 2n\) 범위 내에 항상 소수가 존재한다는 정리다. 이 문제에서는 주어진 \(n\)에 대해 \(n < x \leq 2n\) 범위 내의 소수 개수를 구하는 것이 목표다.

 

단순 소수 판별

나는 이 문제를 해결하기 위해 직접 소수를 판별하는 방식으로 접근했다. 처음에는 가장 단순한 방법으로, 매번 직접 소수를 판별하는 방식으로 구현했다.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def count_primes_in_range(n):
    return sum(1 for i in range(n + 1, 2 * n + 1) if is_prime(i))

while True:
    n = int(input())
    if n == 0:
        break
    print(count_primes_in_range(n))

 

 

하지만 이 방식은 모든 \(n < x \leq 2n\)  범위의 숫자에 대해 is_prime() 함수를 호출하여 소수를 판별하는 구조다. 각 숫자마다 √N 까지 나눠보며 소수 여부를 확인하므로 시간 복잡도가 O(N√N) 이며, 큰 숫자가 들어올수록 연산량이 급격하게 증가한다.

또한, 같은 숫자에 대해 다시 소수 판별을 수행하므로 중복된 계산이 많아지는 문제가 발생한다. 즉, 이미 소수임을 확인한 숫자를 또 판별하는 비효율적인 연산이 이루어진다.

이를 해결하기 위해, 기존에 판별한 소수를 저장하고 활용하는 방식으로 개선해야 한다.

 

소수 리스트 활용

시간 초과 문제를 해결하기 위해 기존에 찾은 소수를 저장하여 활용하는 방식으로 개선했다. 그러나 실행 결과, 출력값이 틀리는 문제가 발생했다.

primes = []

def is_prime(n):
    if n < 2:
        return False
    for prime in primes:
        if prime * prime > n:
            break
        if n % prime == 0:
            return False
    return True

def count_primes_in_range(n):
    global primes
    count = 0
    for i in range(n + 1, 2 * n + 1):
        if is_prime(i):
            primes.append(i)
            count += 1
    return count

while True:
    n = int(input())
    if n == 0:
        break
    print(count_primes_in_range(n))

 

❌ 처음 코드의 문제점

1. 전역 변수 primes가 제대로 갱신되지 않음
   • is_prime(n) 함수는 전역 변수 primes를 참조하지만, count_primes_in_range(n) 함수에서 새로 찾은 소수를 new_primes 리스트에 따로 저장했다.
   • 그러나 is_prime(n)이 new_primes의 값을 참조하지 못해, 소수 판별이 잘못되었고 틀린 결과가 나왔다.
   • 즉, 새로운 소수를 발견할 때마다 primes.append(i)로 바로 추가해야 했지만, 따로 new_primes에 저장하는 바람에 소수 판별이 정확하지 않았다.
2. 초기 소수 리스트(primes)가 비어 있어서 2를 놓침
   • primes = []로 시작했기 때문에, 2를 기본적으로 포함하지 않아 범위 내 소수를 정확히 찾지 못했다.
   • 따라서 2를 판별하지 못해 잘못된 개수를 출력했다.
3. 불필요한 중복 검사가 많음
   • 새로운 소수를 찾을 때마다 primes 리스트를 참조했지만, 이미 판별한 숫자도 다시 검사하는 비효율적인 방식이었다.
   • 불필요한 중복 검사를 피하기 위해 마지막으로 확인한 숫자(last_checked)부터 탐색하도록 수정해야 했다.

 

✅ 문제 해결: 코드 수정 후 정답 도출

이러한 문제를 해결하기 위해 다음과 같이 수정했다:

1. 초기 소수 리스트를 [2]로 시작하여, 2를 기본적으로 포함하도록 설정했다.
2. 새로운 소수를 발견할 때마다 즉시 primes.append(i)로 추가하여, 항상 최신 소수 리스트를 활용할 수 있도록 변경했다.
3. 마지막으로 확인한 숫자(last_checked)를 도입하여 중복 검사를 제거하고, 효율성을 높였다.

primes = [2]

def is_prime(n):
    if n < 2:
        return False
    for prime in primes:
        if prime * prime > n:
            break
        if n % prime == 0:
            return False
    return True

def count_primes_in_range(n):
    global primes
    count = 0
    last_checked = primes[-1]
    for i in range(last_checked + 1, 2 * n + 1):
        if is_prime(i):
            primes.append(i)
    count = sum(1 for p in primes if n < p <= 2 * n)
    return count

while True:
    n = int(input())
    if n == 0:
        break
    print(count_primes_in_range(n))

 

이 방식으로 이전보다 더 빠르게 정답을 도출할 수 있었지만, 여전히 O(N√N)의 시간이 걸리므로 대규모 입력에서는 비효율적이다.

 

에라토스테네스의 체

시간 복잡도를 줄이기 위해 에라토스테네스의 체를 적용하면 O(N log log N)으로 소수를 미리 구할 수 있다. 이 방법을 사용하면 모든 소수를 한 번만 판별하고, 이후 빠르게 조회할 수 있어 훨씬 효율적이다.

 

에라토스테네스의 체에 대한 자세한 설명은 아래 블로그를 참고하면 된다.👇

https://dotz0ver.tistory.com/24

[Algorithm] 에라토스테네스의 체(Sieve of Eratosthenes)란?

 

위 글에서는 소수 리스트를 반환하는 방식으로 에라토스테네스의 체를 설명하고 있다. 하지만 이번 문제에서는 소수 리스트가 아니라 개수만 필요하기 때문에, 불리언 배열을 반환하도록 구현했다.

---

구현

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0], is_prime[1] = False, False
    
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    
    return is_prime

def count_primes_in_range(n, primes):
    return sum(primes[n+1:2*n+1])

MAX_N = 123456
primes = sieve_of_eratosthenes(2 * MAX_N)

while True:
    n = int(input())
    if n == 0:
        break
    print(count_primes_in_range(n, primes))