문제

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제

• 입력

3 16

• 출력

3
5
7
11
13

풀이

check 리스트를 이용해서 n까지의 소수를 판별한다. 소수이면 True, 아니면 False로 리스트를 완성한다.
m부터 n까지의 숫자를 check 리스트에서 찾아서 소수이면 출력한다.

파이썬 코드

""" 요구사항
1. m이상 n이하의 소수를 모두 출력한다.
2. 한 줄에 하나씩 증가하는 순서대로 출력한다.
"""

m, n = map(int, input().split())

check = [False, False] + [True]*(n-1) # 0~16
num = list(range(m, n+1)) # 3~16

for i in range(2, n+1):
    if check[i]:
        for j in range(i*2, n+1, i):
            check[j] = False

for i in num:
    if check[i]:
        print(i)