#백준 4948, 파이썬, 베르트랑 공준, 소수 구하기

# 백준 기본수학2 : 4948번 - 베르트랑 공준

import math

def sosu(n):
  if n ==  1: return False
  for i in range(2, int(math.sqrt(n))+1):
      if n % i == 0:
        return False
  return True


while True:
  n = int(input())
  
  if n == 0 : break # 0 입력하면 종료

  cnt=0
  for i in range(n+1, 2*n+1):
    if sosu(i): cnt+=1

  print(cnt)

시간초과 떴다....

찾아보니 미리 1 ≤ n ≤ 123,456 범위 안에 있는 소수들을 구하고! 입력받은 범위에 해당되는 개수를 세는 방법이 더 좋은 것이었다. 에라토스테네스의 체를 이용했다.

위의 코드는 n을 입력할 때마다 소수가 맞는지 판별해야하니까 시간초과가 뜬듯싶다.

 

# 백준 기본수학2 : 4948번 - 베르트랑 공준

N = 123456*2+1
#에라토스테네스의 체, True이면 소수, False이면 소수 아님
num = [True]*N
for i in range(2, int(N**0.5)+1):
  if num[i]==True:
    for j in range(2*i, N, i):
      num[j] = False


while True:
  n = int(input())
  
  if n == 0 : break # 0 입력하면 종료

  cnt=0
  for i in range(n+1, 2*n+1):
    if num[i]: cnt+=1 #소수 개수 세기

  print(cnt)