백준 - 2839 (Python) - 베르트랑 공준

베르트랑 공준

백준 2839

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

인풋의 첫 번째 줄에는 테스트 케이스의 횟수가, 끝 줄에는 0이 입력된다.
여러 개의 테스트 케이스가 주어지다가 0이 나타나면 끝나는 방식.

이 문제는 "에라토스테네스의 체"를 사용하는 것이 좋다는 조언을 들어서, 미리 에라토스테네스의 체 파이썬 응용 --> 이 곳에서 파이썬으로 표현하는 방법에 대해 서술해 놓았다.

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)

코드를 보면 미리 최대 n(<=123456)의 소수를 모두 구해 놓아 처리 시간을 단축시킬 수 있다.

앞서 사용했던 에라토스테네스의 체를 이용하여 모든 소수를 구하고, n+1 <= x <= 2n 범위의 소수를 세어주면 끝!