백준 4948 - 베르트랑 공준 (파이썬)

Answer

import sys

def Binary_Search(prime, n):
    l = 0
    r = len(prime) - 1
    while l <= r:
        m = (l + r) // 2

        if prime[m] > n:
            r = m - 1
        else:
            l = m + 1
    return l
    
sieve = [True] * 246913

for i in range(3, int(246913 ** 0.5) + 1, 2):
    if sieve[i]:
        sieve[i ** 2::i * 2] = [False] * ((246913 - i ** 2 - 1) // (i * 2) + 1)

x = [2] + [i for i in range(3, 246913, 2) if sieve[i]]

while True:
    m = int(sys.stdin.readline())
    if m == 0:
        break
    else:
        print(Binary_Search(x, 2 * m) - Binary_Search(x, m))