백준-1929 소수 구하기 (에라토스테네스의 체)

문제

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

풀이

에라토스테네스의 체를 이용해서 풀어보자. N까지의 수를 모두 소수라 가정하고 가장 큰 수의 제곱근 + 1 까지의 소수들의 배수들을 모두 false로 만들면 된다! 그리고 1은 소수가 아니므로 false로 만들자!!!

 

M, N = map(int, input().split())

a = [True] * (N + 1)
b = int((N+1) ** 0.5) + 1
a[1] = False
for i in range(2, b):
    if a[i]:
        for k in range(i + i, N + 1, i):
            a[k] = False

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