⌛ 4948번 베르트랑 공준

📌 문제

4948번 베르트랑 공준

📝 코드

처음에는 아래의 코드처럼 각각의 경우마다 소수의 개수를 구해줬더니 시간 초과가 발생하였다.

while True:
  n = int(input())
  if n == 0:
    break

  prime_list = []
  for num in range(2, 2 * n + 1):
    check = True
    for prime in prime_list:
      if prime * prime > num:
        break
      if num % prime == 0:
        check = False
        break
    if check == True:
      prime_list.append(num)

  result = 0
  for prime in prime_list:
    if prime > n and prime <= 2 * n:
      result += 1
  print(result)

그래서 먼저 주어진 제한 범위 안의 소수들을 모두 구해 prime_list에 넣고 나서 입력받은 n 값에 따라 해당 범위 안의 소수의 개수를 count 하는 방식을 사용하였다.

prime_list = []
for num in range(2, 123456 * 2):
  check = True
  for prime in prime_list:
    if prime * prime > num:
      break
    if num % prime == 0:
      check = False
      break
  if check == True:
    prime_list.append(num)

while True:
  n = int(input())
  if n == 0:
    break
  
  count = 0
  for prime in prime_list:
    if prime > n and prime <= 2 * n:
      count += 1
  print(count)