[Algorithm] 1일1솔 - 백준 1929 소수구하기 (python3)

문제링크

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

1929번: 소수 구하기

 

문제풀이

에라토스테네스의 체 기반으로 풀었다. m, n이 1부터 입력될 수 있기 때문에 sieve의 0, 1을 False로 초기값을 설정해야 한다.

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

print(*[i for i in range(m,n+1) if sieve[i] == True], sep='\n')