- 각 테스트케이스별 모든 수를 검사해 소수를 찾지 않고,
에라토스테네스의 체를 활용해 해당 범위 내 모든 소수를 미리 찾아 표시해 놓았다.
- 각 테스트케이스 별 범위에서 표시한 소수를 찾아 출력함으로써 시간 을 단축했다.
👉 [백준 4948 파이썬] - 베르트랑 공준
// 에라토스테네스 체 활용 부분 --------------------------------------------------------
N = 123456 * 2 + 1
sieve = [True] * N
for i in range(2, int(N**0.5)+1):
if sieve[i]:
for j in range(2*i, N, i):
sieve[j] = False
// -----------------------------------------------------------------------------
def prime_cnt(n):
cnt = 0
for i in range(n+1, n*2+1):
if sieve[i]:
cnt += 1
print(cnt)
while True:
n = int(input())
if n == 0:
break
prime_cnt(n)