[1929] 소수 구하기*

문제

• M이상 N이하의 소수를 모두 출력하는 프로그램을 작성

• 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어짐 (1 ≤ M ≤ N ≤ 1,000,000)

• 기존의 함수를 이용해서 문제를 풀었으나 시간초과가 발생했다.
• 에라토스테네스의 체를 이용
  • 무식하게 배수들을 지워나가는 방식이지만, 그만큼 빠르게 작동 할 수
• 만약 어떤 수 $m=ab$라면, $a$와 $b$중 적어도 하나는 $\sqrt{n}$이하이므로, $n$보다 작은 합성수 $m$은 $\sqrt{n}$보다 작은 수의 배수만 체크해도 전부 걸러질 수 있음. 따라서 $\sqrt{n}$이하의 수의 배수만 지우면 됨.

정답

import sys
import math

def isprimenum(num):
    if num <= 1:
        return 0
    for j in range(2, int(math.sqrt(num))+1):
        if num/j == 1:
            break
        if num%j == 0:
            return 0
    return 1

nums = list(map(int, sys.stdin.readline().split()))
for j in range(nums[0], nums[1]+1):
    if isprimenum(j)==1:
        print(j)