두 가지 소수 판정법

PS에서 자주 사용하는 소수 판정법 두 가지를 소개한다. 문제에 따라 두 가지 중 어떤 판정법을 사용할지 결정해야 할지 시간복잡도를 통해 해결해보자 주제 Trial Division 직접 나누는 방식이다. 만약 N을 소수판정 한다고 할 때, 2부터 N-1까지의 모든 숫자로 나눠보며, 만약 한번이라도 나눠진다면 N은 소수가 아니다. 아니라면 소수다. 하지만 2부터 N-1까지 나누는 알고리즘은 사용할 필요가 없다. N이 100일 때, 20으로 나누는 상황을 생각해보자. 100 / 20 = 5 이다. 하지만 100은이전에 5로 나눔으로써, 100은 20으로 나눠짐이 확인되었으므로 굳이 나눌 필요가 없다. 때문에 sqrt(N), 즉 루트 N 까지만 나눠보면 된다. 2부터 sqrt(N)까지 1씩 증가하며 나누므로, 시간복잡도는 O(sqrt(N)) 이 된다. Sieve of Eratosthenes 에라토스테네스의 체다. 내가 아무리 설명해도 나무위키 보다 잘 설명할 자신이 없으므로, 나무위키를 ...

원문링크 : 두 가지 소수 판정법