[Python] 백준 파이썬 4948 베르트랑 공준

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

바로 전에 푼 소수 구하기 문제랑 비슷하게 생각해서 첫 시도를 해봤습니다.

# 백준 4948 베르트랑 공준
# 소수 찾는 함수 정의
def prime(x):
  if x == 1:
    return False
  for i in range(2, int(x**0.5)+1):
    if x % i == 0:
      return False
  return True

while True:
  n = int(input())
  count = 0
  if n == 0:
    break
  for i in range(n+1, 2*n+1):
    if prime(i):
      count += 1
  print(count)

어김없이 시간 초과가 났습니다.

매번 계산 하는게 힘든 것 같아서 미리 주어진 n의 범위에 해당하는 소수 리스트를 만들어놓고

꺼내면서 확인 하는 방법을 사용했습니다.

메모이제이션이랑 비슷(?)한 방법입니다.

def prime(x):
  if x == 1:
    return False
  for i in range(2, int(x**0.5)+1):
    if x % i == 0:
      return False
  return True

# 1 <= n <= 123,456
# 2 <= 2*n <= 246912
n_list = list(range(1,246913))
prime_list=[]
for i in n_list:
  if prime(i):
    prime_list.append(i)

while True:
  n = int(input())
  count = 0
  if n == 0:
    break
  for i in prime_list: # 만들어 둔 소수 리스트에서 숫자 꺼내서 비교
    if n < i <= 2*n:
      count += 1
  print(count)