알고리즘
[백준] 1929 소수구하기
유노비
2023. 10. 17. 22:21
반응형
import math
n, m = map(int, input().split())
result = set(range(n,m+1))
for i in range(2, int(math.sqrt(m))+1): # 2 ~ 루트M(=M의 약수들 중에서 중간값) 까지 증가시킨다. (<-에라토스테네스의 체 방식)
remove_element = set(range(i,m+1,i)) # 2~ 루트M까지의 수의, 배수 set 을 생성
remove_element.discard(i)
result = result - remove_element # 2~ 루트M까지의 수의, 배수를 제거한다
result.discard(1) # 1이 포함되어있을 경우 삭제하기
result = sorted(list(result)) # 오름차순 정렬하기
print(*result, sep='\n')
반응형