Stage_9 (기본수학2) 4948번 베르트랑 공준

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

 

#숫자 N까지 소수 개수 구하는 함수

 

def isPrimeBelow(N):

  sieve = [1] * (N+1)

  sieve[0] = 0

  sieve[1] = 0

 

  for i in range(2, int(N**0.5)+1):

    if sieve[i] == 1:

      for j in range(i+i, N+1, i):

        sieve[j] = 0

  return sieve

 

#가장 큰 숫자까지 미리 소수를 구해놓기

 

prime_list = isPrimeBelow(246913)

 

for i in range(123457):

  N = int(input())

  if N == 0: break

  

  print(prime_list[N+1:2*N+1].count(1))

 

 

## Comment1 : 여러 숫자에 대해 Input을 받으므로 처음부터 소수 전체 List를 작성하는 것이 Point! 이전 문제와 같이 input 받은 숫자 대로 소수 판별 함수에 넣고 돌리면 시간 초과가 뜬다.

## Comment2 : 함수를 사용하는 것은 좋으나 이것이 여러번 호출되지는 않는지 확인이 필요하다