[알고리즘] 특정 구간 소수 ( 에라토스테네스의 체 )

m, n = int(input()), int(input()) # 구간을 입력받는다

bool = [False, False] + [True]*(n-1) # 0과 1은 소수가 아니므로 False를 넣어둔다

for i in range(2, int(n**.5)+1):
    if bool[i]:
        for index in range(i*2, n+1, i):
            bool[index] = False # i의 배수에 False를 넣어준다
            
print([i for i in range(m, n+1) if bool[i]]) # m부터 n까지의 구간에서 bool[i]가 True인 값만 출력

 

# 입력값
3
20

# 출력값
[3, 5, 7, 11, 13, 17, 19]