[1929] 소수 구하기 (에라토스테네스 방식, 2부터 배수 제거)

1929번: 소수 구하기

 

분석

• 1 ≤ M ≤ N ≤ 1,000,000 이므로 일반적인 소수 구하기 방식으로 풀면 시간 초과 발생 ➔ 에라토스테네스 채
• N의 제곱근까지만 탐색하는 이유
  • N의 제곱근이 n일 때 N=a*b를 만족하는 a b 전부 다 n보다 클 수 없음
  • N보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가짐
  • 에라토스테네스의 체로 n이하의 수의 배수를 모두 제거하면 1부터 N사이의 소수를 구할 수 있음

N=16, n=4
a, b= (1,16),(2,8),(4,4)(8,2),(16,1)
N보다 작은 소수가 아닌 수 : 1, 4, 8, 10, 12, 14, 16
N보다 작은 소수 : 2, 3, 5, 7, 9, 11, 13, 15

 

풀이

import math
# M이상 N 이하의 소수를 모두 출력 (1 ~ 1,000,000)
m, n = map(int, input().split())

# 에라토스테네스 방식 : 배수 지우기
list = [0] * (n+1)

for i in range(2, n+1):
    list[i] = i

# 제곱근까지만 수행 : n보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가짐
for i in range(2, int(math.sqrt(n))+1):
   if list[i] == 0:
       continue
   for j in range(i+i, n+1, i):
       list[j] = 0

for i in range(m, n+1):
    if list[i] != 0:
        print(list[i])