백준 4948 파이썬 - '에라토스테네스 체'

코드

N = 2*123456+1
sosu =[True] *N

for i in range(2,int(N**0.5)+1):
  if sosu[i]:
    for j in range(2*i,N,i):
      sosu[j] = False

def check_prime(n):
  cnt = 0
  for k in range(n+1, (n*2)+1):
    if sosu[k]:
      cnt += 1
  print(cnt)

while 1:
  n = int(input())
  if n == 0 :
    break
  check_prime(n)

N의 범위는 1<=N<=123456 이며, 우리는 입력된 n에 대해서 n보다 크면서 2n까지의 수 중에서 소수의 개수를 구해야한다. 
변수 N에 123456*2+1 크기를 지정하여 최대 범위의 수까지의 소수를 '에라토스테네스 체' 방식으로 구한다.
for i in range(2, int(N**0.05)+1) 을 통해 N까지 모두 반복문을 돌리는 것이 아니라 N의 제곱근 값 +1 한 값까지만 소수인지 검사하여 시간 복잡도를 고려한다. ex) 16의 약수는 1,2,4,8,16이며 중간에 있는 4를 제외하고 모두 짝을 짓고 있다. 그러므로 16의 제곱근보다 1 큰 수까지 소수 검사를 했을 때 나누어지는 수가 없다면 그 수는 소수라고 할 수 있습니다.)
그리고 다음 2중 반복문에서 for j in range(2*i,N,i) sosu[j] = False 를 통해 소수가 아닌 수들을 걸러낸다.

시간 초과된 코드

def prime(n):
  i = 2
  global cnt
  if n == 1:
      return
  while i <= n:
    if n == i :
      cnt += 1
      return
    if n % i == 0:
      return
    i += 1

while 1 :
  n = int(input())
  cnt = 0
  if n == 0 :
    break
  n2 = n*2
  while n <= n2:
    prime(n)
    n +=1 
  print(cnt)