문제

풀이

에라토스테네스의 체를 이용하는 문제이다. 값이 모두 True인 리스트를 만들고 1은 소수가 아니므로 False를 저장한다. 2부터 n의 제곱근까지 반복하면서 n보다 작거나 같은 i의 배수를 False로 바꾼다. m부터 n까지 num[i]가 True면 출력한다.

import sys
from math import sqrt

def input():
    return sys.stdin.readline().rstrip()
    
m, n = map(int, input().split())
num = [True] * (n+1)
num[1] = False

for i in range(2, int(sqrt(n)) + 1):
    if num[i] == True:
        j = 2
        while i * j <= n:
            num[i * j] = False
            j += 1

for i in range(m, n+1):
    if num[i]:
        print(i)