[알고리즘/백준] 1929: 소수 구하기(python)

에라토스테네스 체를 사용해서 풀었다.
약수를 이용하면 시간을 많이 줄일 수 있다.

import math
k = 1000000
M, N = map(int, input().split())
a = [False, False] + [True] * 1000000
for i in range(2, int(math.sqrt(k+1))+1):
    if a[i]:
        for j in range(2*i, k+1, i):
            a[j] = False

for i in range(M, N+1):
    if a[i]:
        print(i)