[BaekJoon] 1929번 : 소수 구하기

1929번 : 소수 구하기

솔직히 에라토스테네스의 체를 제대로 완벽히 이해했다고 생각하지 않고 풀었던 문제였다..

그래서 다시 풀게 되었는데 이번엔 완벽히 이해했다..

소수 판별에 있어서 에라토스테네스의 체가 무조건 완벽한 알고리즘은 아니다.

수 범위가 백만 내외 일 경우 사용하자.

---

from math import sqrt


def solution():
	prime = [True] * (N + 1)
	prime[1] = False

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

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


if __name__ == '__main__':
	M, N = map(int, input().split())

	solution()