[백준 - python] 4948번: 베르트랑 공준

<문제 링크>

4948번: 베르트랑 공준

 

<문제 풀이>

while 1:
  n = int(input())

  if n == 0:
    break

  cnt = 0
  for i in range(n+1, 2*n+1):
    if i == 2:
      cnt += 1
    else:  
      for j in range(2, int(i**0.5)+1):
        if i % j == 0:
          break
      else:
        cnt += 1

  print(cnt)

처음에는 위와 같은 방식으로 문제를 풀었으나 시간 초과가 발생하였다. input 함수를 sys모듈의 함수로 대체하여도 시간 초과가 발생한 것으로 보아 무분별한 반복문의 사용이 문제로 보였다.

 

 

prime_num = [2]

for i in range(3, 123456*2):
  for j in range(2, int(i**0.5)+1):
    if i % j == 0:
      break
  else:
    prime_num.append(i)

while 1:
  n = int(input())

  if n == 0:
    break
  
  cnt = 0
  for num in prime_num:
    if n < num <= 2*n:
      cnt += 1

  print(cnt)

입력된 숫자에 따라 계속해서 소수를 구하는 것이 아닌 미리 구해놓은 소수 리스트에서 범위 내에 존재하는 소수 수를 구하는 방식으로 변경하였다.

4948 입출력 예시

*key point: 2 ~ 제곱근까지만 나누어 보는 것만으로도 소수임을 판별 가능하다. 1은 소수가 아니며, 2는 소수이지만 알고리즘에 포함시키기 어려움을 고려해야한다. 언제나 실행 시간을 최소화 하기 위한 알고리즘을 계속해서 고민해보아야 한다.