[Python] 백준 <4948-베르트랑 공준>

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

 

import sys
import math
input = sys.stdin.readline

while True:
    N = int(input())

    if N == 0:
        break

    maxN = 2*N
    is_prime = [True for x in range(maxN+1)]
    p = 2
	
    # 에라토스테네스의 체 알고리즘 이용
    while p*p <= maxN:
        if is_prime[p]:
            for i in range(p*p, maxN+1, p):
                is_prime[i] = False
        p += 1
    
    dap = [p for p in range(N+1, maxN+1) if is_prime[p]]
        
    print(len(dap))