BOJ #4948 베르트랑 공준

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 4948. 베르트랑 공준

문제 풀이

시간제한이 1초다. 소수 판정은 2부터 입력값의 제곱근까지 나눴을 때 나누어지지 않으면 소수라고 판정할 수 있다. 그러나 모든 케이스에 대해 매번 계산을 진행하면 n + 1 ~ 2n까지의 값에 대해 매번 계산해야 하므로 사실상 시간복잡도는 $O(n\cdot \sqrt n)$이다. 소수 판정 코드엔 문제가 없지만 이 문제에서 주어지는 모든 입력값을 출력하는 데 소요되는 시간이 문제의 제한시간보다 초과되면 안되기 때문에 매번 값이 입력될 때마다 계산하면 시간초과가 발생한다. 입력값 범위를 보면 123,456까지라고 명시되어 있다. 그렇다면 123456 * 2까지의 소수를 모두 판별해두고 입력값이 들어올 때마다 n + 1 ~ 2n까지의 수 중에 True로 마킹된 원소만 세주면 된다.

값의 범위가 정해져 있고 각 케이스마다 별도로 계산할 필요 없이 전체 범위에 대해 계산해두면 하나의 맵에서 범위를 지정해 조회만 하면 되는 문제이므로 사용할 수 있는 방법이다. 시간복잡도는 $O(n\cdot log\ n)$이 된다.

python 코드

import sys

N = 123456 * 2 + 1 // input 값의 범위 : 123456
sieve = [True] * N // 에라토스테네스 체 맵 생성
sieve[0] = False // 1은 소수가 아님
// 에라토스테네스 체 생성 - 복잡도 log n
for i in range(2, int(N ** 0.5) + 1):
    if sieve[i]:
        for j in range(2 * i, N, i):
            sieve[j] = False
// 입력값에 0이 입력될 때 까지
while True:
    v = int(input())
    if v == 0:
        break
    cnt = 0
    for n in sieve[v + 1: v * 2 + 1]:
        if n == True:
            cnt += 1
    print(cnt)