https://www.acmicpc.net/problem/4948
시간 2초, 메모리 256MB
input :
- 여러 개의 테스트 케이스
- 케이스는 n을 포함하는 한 줄
- 입력의 마지막에는 0
output :
- n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력
n보다는 크다. 즉 n + 1에서 시작해서 2n을 포함해야 하니까 2n + 1까지 반복문을 실행.
import sys
from math import sqrt
prime_number = [1] * 300001
prime_number[0] = prime_number[1] = 0
for i in range(2, int(sqrt(300001))):
for j in range(i * i, 300001, i):
if prime_number[j]:
prime_number[j] = 0
while True:
n = int(sys.stdin.readline())
if n == 0:
break
ret = []
for i in range(n + 1, 2 * n + 1):
if prime_number[i]:
ret.append(i)
print(len(ret))
