[BOJ] 4948 베르트랑 공준

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

1929 소수 구하기 에서 사용했던 에라토스테네의 체를 사용하면 될 것 같다. 입력을 받을 때마다 소수를 구하면 런타임 에러가 나기 때문에 입력을 한번에 받아서 최대값 기준으로 필요한 만큼만 구한다.

[Code]

inputs = []
while True:
    input_str = int(input())
    if input_str == 0:
        break
    else:
        inputs.append(input_str)

n_max = max(inputs)
arr = [False, False] + [True] * (n_max * 2 - 1)

for i in range(2, 2 * n_max + 1):
    if arr[i]:
        for _ in range(i*2, 2 * n_max + 1, i):
            arr[_] = False

for n in inputs:
    count = 0
    for i in range(n+1, 2*n+1):
        if arr[i]:
            count += 1
    print(count)