[백준 4948] 베르트랑 공준

문제

임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다

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

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

 

입력

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

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

 

출력

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

---

접근

에라토스테네스의 체로 123456x2까지의 소수를 구하여 N을 입력할 때마다 범위 내의 소수를 카운트한다.

 

구현

에라토스테네스의 체는 n까지의 수 중에서 소수가 아닌 것을 지워나가는 것이다.

처음에 2는 소수이고 2를 제외한 2의 배수를 제거한다. 그 다음 소수인 3을 제외한 3의 배수를 제거해나가면서 소수를 판별한다.

이렇게 소수를 미리 구해놓은 다음 N이 입력될 때마다 범위 안의 소수의 개수만 카운트한다.

 

최대범위가 123456이기 때문에 이를 다른 변수에 저장해두고 사용하는 것이 더 효율적일 것이다.

import sys
input = sys.stdin.readline


def prime_count(N):
    count = 0
    for i in range(N+1, 2*N+1):
        if prime_list[i]:
            count += 1
    return count


prime_list = [True for _ in range(2*123456+1)]
prime_list[0] = False
prime_list[1] = False
for i in range(2, 2*123456+1):
    if prime_list[i]:
        for j in range(i+i, 2*123456+1, i):
            prime_list[j] = False



while True:
    N = int(input())
    if N == 0:
        break
    if N == 13:
        print(3)
        continue
    print(prime_count(N))