문제
https://www.acmicpc.net/problem/1929
Lesson 1929: 소수 찾기
'추천 관련글,
첫 번째 줄에는 자연수 M과 N이 사이에 공백이 있습니다. (1 ≤ M ≤ N ≤ 1,000,000) M과 N 사이의 소수가 하나 이상 있는 항목만 제공됩니다.
www.acmicpc.net
설명
m보다 크거나 같고 n보다 작거나 같은 모든 소수를 반환합니다.문제입니다.
에라토스테네스의 체 알고리즘은 솔루션을 용이하게 합니다.
https://dev-mandos.93
(알고리즘) 에라토스테네스의 체(Swift)
에라토스테네스의 체 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 개발한 소수를 찾는 알고리즘입니다. 체처럼 물을 걸러낸다고 하여 “에라토스테네”라고 합니다.
dev-mandos.tistory.com
n보다 작은 소수를 모두 찾은 후
m 이상 n 미만 프라임이면 하나씩 체크해서 출력할 수 있어요.
소스 코드
검토
소수점 판별의 논리알면 쉽게 해결할 수 있습니다.
에라토스테네스의 체 알고리즘을 사용하지 않고 소수를 개별적으로 구별당신은 그렇게 할 수 있습니다.
하지만 에라토스테네스의 체 알고리즘을 사용하여 동시에 n보다 작거나 같은 소수를 찾는 것이 더 빠릅니다.
