#150 백준 파이썬 [4948] 베르트랑 공준

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

 

#Solution

에라토스테네스의 체를 이용하여 소수를 구해준 다음, 맞는 소수의 개수를 출력하는 방법이 가장 빠르다.

import sys


#소수리스트 만들어주기
prime_ox = [True for _ in range(123457 * 2)]

for i in range(2, int((123457 * 2) ** 0.5)):
    if prime_ox[i] == True:
        for j in range(i+i, 123457 * 2, i):
            prime_ox[j] = False 

prime_list = [i for i, j in enumerate(prime_ox) if j == True and i >=2 ]


#소수 출력하기
num = int(sys.stdin.readline())

while num != 0:
    
    answer = 0
    for i in prime_list:
        if i <= num :
            continue
        elif num * 2 >= i > num:
            answer += 1
        else:
            break
            
    print(answer)
    
    num = int(sys.stdin.readline())