백준 알고리즘 4948 (베르트랑 공준) - python

[문제] 백준 알고리즘 4948 (베르트랑 공준)

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

4948번: 베르트랑 공준

 

임의의 자연수 n에 대해 n < x <= 2n 을 만족하는 소수 x의 갯수를 구하는 문제.

여러 개의 테스트 케이스가 주어지다가, 0이 나타나면 끝나게 된다.

 

그래서, 미리 최대 n(<=123456)의 소수를 모두 구해 놓아서 시간을 효율적으로 썼다.

앞서 사용했던 에라토스테네스의 체를 이용하여 모든 소수를 구하고,

n+1 <= x <= 2n 범위의 소수를 세어준다. (n이 자연수이므로 1은 상관하지 않아도 됨.)

 

[Code]

N = 123456 * 2 + 1
sieve = [True] * 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

def prime_cnt(val):
    cnt = 0
    for i in range(val + 1, val * 2 + 1):
        if sieve[i]:
            cnt += 1
    print(cnt)

while True:
    val = int(input())
    if val == 0:
        break
    prime_cnt(val)