[백준] 4948 베르트랑 공준

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

tmp = 123456*2
prime=[False,False]+[True]*(tmp)
for i in range(2,int(tmp**0.5)+1):
    if prime[i]:
        for j in range(2*i,tmp+1,i):
            prime[j]=False

while True:
    n = int(input())
    if n == 0:
        break
    print(prime[n+1:2*n+1].count(True))

이번엔 에라토스테네스의 체를 사용할때 범위를 줄였다. ㅋㅋ

tmp는 제한 숫자의 두배 되는 값이다.

에라토스테네스의 체로 최대 숫자까지 미리 소수를 구해놓고 구간을 슬라이싱 하여 True의 개수를 출력했다.