[1. 개요]
어떠한 자연수가 소수인지 판별 할 수 있는 방법에 대해 정리한다.
[2. 알고리즘]
- 단순한 방법
=> 소수는 1과 자기자신으로만 나누어 떨어지므로,
=> 2 부터 N-1 까지의 자연수 중 나누어 떨어지는 것이 있는지 확인 한다.
=> 단일 자연수 N에 대해서 시간 복잡도는 O(N) 이 된다. - N 의 절반까지만 확인
=> - N 의 제곱근 까지만 확인
=>
[3. 에라토스테네스의 체]
특정 범위 내 모든 소수를 찾을 때 매우 유용하다.
시간 복잡도가 O(nlog(logn)) 이다.
원리
- 최초 모든 수를 소수라 가정
- '1'은 소수가 아니라고 망킹
- '2' 는 소수이므로, 2의 배수를 모두 소수가 아니라고 마킹
- '3' 은 소수이므로, 3의 배수를 모두 소수가 아니라고 마킹
- 다음 수 에 대해서 반복,
=> 이번에 확인 할 수가 소수라고 마킹 된 것에 한해서