백준 알고리즘 4938번 베르트랑 공준(python)

이 문제 또한 저번에 봤던 에라토스테네스의 체를 사용해 쉽게 풀 수 있다.

while True:
    n = int(input())
    if n == 0:
        break
    n1, n2= n+1, 2*n
    li = [1]*(n2+1)
    for i in range(2, int((n2+1)**0.5) + 1):
        if li[i] == 1:
            for j in range(i+i, n2+1, i):
                li[j] = 0
    cnt = 0
    for i in range(n1, n2+1):
        if li[i] == 1 and i > 1:
            cnt += 1
    print(cnt)