백준 / 베르트랑 공준 / 4948

Question

문제링크
Silver 2

Logic

기본 구조 : 에라스토테네스의 체
1. 최대 가능수인 246913까지 에라스토테네스의 체를 이용해 미리 소수 리스트를 구한다.
2. 이 때 246913까지 인덱스를 두고 소수의 경우 1, 아닌 경우 0으로 표기한다.
3. 입력 받은 수 부터 2n까지 1의 갯수를 출력한다.

Code

from sys import stdin
import math

prime = [0,0]+[1 for _ in range(246913)]

for i in range(2,int(math.sqrt(246913))+1):
    if prime[i]==0 : continue
    j=i
    while j <= 246913:
        j+=i
        if j > 246913 : break
        prime[j]=0
        

N = int(stdin.readline())
while(N!=0):
    print(prime[N+1:2*N+1].count(1))
    N = int(stdin.readline())