Let IT Begin

* 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$의 ..