[백준] 4948번(베르트랑 공준)

백준 4948번

제출 코드(오답)

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

number_list = list(range(2, 123456*2+1))
prime_list = []

for i in number_list:
  check = True
  if i==1: check=False
  check = check_prime(i)

  if check==True:
    prime_list.append(i)
    

while True:
  number = int(input())
  if number==0:
    break
    
  count = 0

  my_list = list(range(number+1,(number*2+1)))
  
  for i in my_list:
    if i in prime_list:
      count+=1

  print(count)

• 시간초과 문제를 해결하기 위해
  1) 소수인지 확인하는 부분을 중첩 반복문이 아닌 함수로 선언
  2) 주어진 입력에 따라 해당하는 범위 내 소수들을 리스트로 저장
• 하지만 여전히 시간초과로 뜸

다른 사람이 작성한 코드

import math

k = 123456*2+1
num_list = [1]*k

for i in range(1,k):
  if i==1:
    continue
  for k in range(2, int(math.sqrt(i))+1):
    if i%k==0:
      num_list[i]=0
      break
      
while True:
  n = int(input())
  sum=0
  if n==0:
    break
  for i in range(n+1, 2*n+1):
    sum += num_list[i]
  print(sum)

• 내가 작성한 코드와 논리는 동일
• 범위 내 소수의 개수를 구하기 위해 이용하는 리스트 생성 방식과 범위 내 소수의 개수를 구하기 위해 리스트를 탐색하는 방식만 다름!
• 게다가 이 코드에서는 중첩 반복문 사용!

다른 사람이 작성한 코드(수정)

import math

k = 123456*2+1
num_list = list(range(2, k))

for i in range(1,k):
  if i==1:
    continue
  for k in range(2, int(math.sqrt(i))+1):
    if i%k==0:
      num_list.remove(i)
      break
      
while True:
  n = int(input())
  count=0

  if n==0:
    break

  my_list = list(range(n,(n*2+1)))
  
  for i in my_list:
    if i in num_list:
      count+=1

  print(count)

• 정답 코드에 리스트 생성 방식만 내가 사용한 방식으로 변경하여 제출했더니 역시나 시간초과라고 뜸
• 정답 코드는 리스트를 생성할 때 num_list = [1]*k으로 생성하지만
  내가 작성한 코드는 리스트를 생성할 때 number_list = list(range(2, 123456*2+1))처럼 range()를 사용해서 그런게 아닌가 추측중...
• 정확한 원인은 아직 모르겠다...

코드 출처