[Algorithm] 소수 판별 - 밀러-라빈 판정법
* Python을 기준으로 합니다소수 판별 - 밀러-라빈 판정법 (Miller-Rabin Primality Test)- 개념밀러-라빈 소수 판정법간단한 소수 판별은 $O(\sqrt{n})$의 time complexity를 가지고, 에라토스테네스의 체를 사용하면 $O(n \log \log n)$으로 개선 가능 하지만, 여전히 상당히 큰 수에 대해서는 소수 판별을 적용하기 어려움밀러-라빈 판정법은 기존 소수 판별법들과 달리 결정론적으로 동작하지 않고 확률적으로 동작하지만, 상당히 빠른 time complexity를 달성할 수 있음- 이때 $n 이론적 유도먼저 모든 짝수는 2를 제외하면 소수가 아니므로 $n$을 홀수인 소수라고 가정하자그러면 $n-1$을 정수 $s$에 대해 짝수 $2^{s}$와 홀수 $d$의 ..
[Algorithm] 소수 판별 - 에라토스테네스의 체
* Python을 기준으로 합니다소수 판별 - 에라토스테네스의 체 (Sieve of Eratosthenes)- 개념소수 : 2보다 큰 자연수 중 1과 자기 자신 만을 약수로 가지는 수기본적으로 완전 탐색을 사용할 수 있지만, $O(n)$의 time complexity가 소모되므로 큰 수에 대해서는 비효율적임- 이때 자연수의 약수는 대칭적으로 구해진다는 것을 고려하면, $O(\sqrt{n})$의 time complexity로 줄일 수 있음에라토스테네스의 체 : $N$ 보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있고, $O(n \log \log n)$의 time complexity를 가짐에라토스테네스의 체 동작과정2부터 $N$까지의 모든 자연수를 나열남은 수 중에서 처리되지 않은 가장 작은 자연수 $..