[백준] 1929: 소수 구하기

에라토스테네스의 체를 이용하여 푼 문제 입니다.

문제풀이전략
1. 일단, 모든 수를 소수라고 가정하는 prime 리스트를 만듭니다.
2. (1 ≤ M ≤ N ≤ 1,000,000)
3. 2부터 (n의 제곱근 +1) 까지 prime number가 True이면
배수를 전부 False로 바꾸어줍니다.
4. m부터 n 까지 True인 값의 인덱스를 출력해줍니다.

from collections import Counter
import sys
import math
input = sys.stdin.readline
m, n = map(int, input().split())
prime = [True for _ in range(1000001)]
print(prime[19])
prime[1] = 0
for i in range(2, int(math.sqrt(n))+1):
	if prime[i] == True:
		# print('pp',m)
		x = 2
		while i * x <= n:
			prime[i * x] = False
			x += 1
for i in range(m, n+1):
	if prime[i] == True:
		print(i)