[Python] 소수 구하기 - 백준

해당 글은 백준 1929번 문제 '소수 구하기'을 다룬다.

문제

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

설명

소수를 구하는 해당 문제는 에라토스테네스의 체를 이용하면 쉽게 풀수있다는 도움을 받았다.

에라토스테네스의 체는 11보다 작은 배수들의 값을 지우면 소수만 남는 방법이다.

해당 문제에서 이전에 지웠던 값을 중복해서 지운다면 런타임에러가 뜬다.

그러므로 if문을 통해 이전에 지운 값은 다시 검사하지 않도록 해야한다.

 

에라토스테네스의 체

 

코드

m, n = map(int, input().split())
result = [True]*1000001
result[1] = False
for i in range(2, n+1):
    if result[i]:
        for j in range(i+i, n+1, i):
            result[j] = False

for i in range(m, n+1):
    if result[i]:
        print(i)