BOJ-4948 (Silver II)

https://www.acmicpc.net/problem/1929 에서 풀었던대로 하면 똑같이 시간제한 안에 해결될 것이라 생각했는데 시간이 초과되었다. 이를 해결하기 위해 문제에서 제시한 제한사항을 고려하기로 했다.

이전 방식은 인풋이 들어올때마다 범위내 소수를 계산했는데 이러면 소수를 여러번 반복해서 구하게된다. 이것을 방지하기 위해서 제한범위인 1~123456*2 이내의 모든 소수를 구해 리스트업하고 그 리스트와 대조하면 반복을 없앨 수 있다.

import sys

def is_prime(x):
  if x==1: return False
  sq = int(x**0.5)

  for i in range(2, sq+1):
    if x%i==0: return False
  
  return True

# 값들어올때마다 반복하지 말고 미리 제한범위내 모든 #소수를 미리 계산
num_list = []
for i in range(1,123456*2+1):
  if is_prime(i): num_list.append(i)


while 1:
  n = int(sys.stdin.readline())
  if n==0: 
    break
  cnt=0
  for i in num_list:
    if n < i <=2*n: 
      cnt+=1

  print(cnt)