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

코드

에라토스테네스의 체를 이용하면 간단하게 해결 가능하다.

import math
while True:
    n = int(input())
    if n == 0:
        break

    count = 0
    check = [True]* (2 * n + 1) # 모든 수가 소수 라고 가정
    for i in range(2, int(math.sqrt(2*n) + 1)):       
        if check[i]:
            j = 2
            while i * j <= 2*n:
                check[i*j] = False
                j += 1
    for x in range(n+1, 2*n +1):
        if check[x]:
            count += 1
    print(count)