From f6b6c4c8694cd398b67ac0c2b4ad4fdf0b782c58 Mon Sep 17 00:00:00 2001 From: JBatzill Date: Tue, 1 Dec 2015 13:50:20 +0100 Subject: Added miller rabin implementation tested with big primes <= 10^18 from wikipedia and solved problem: https://open.kattis.com/problems/primes2 --- math/miller_rabin.cpp | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) create mode 100644 math/miller_rabin.cpp diff --git a/math/miller_rabin.cpp b/math/miller_rabin.cpp new file mode 100644 index 0000000..ad8c163 --- /dev/null +++ b/math/miller_rabin.cpp @@ -0,0 +1,20 @@ +//theoretical: n < 318,665,857,834,031,151,167,461 ( > 10^23) +//but: n ~<= 10^18 (because of MAX(ll)) +//O(logn) +bool isPrime(ll n) { + if(n == 2) return true; + if(n < 2 || n % 2 == 0) return false; + ll d=n-1,j=0; + while(d % 2 == 0) d >>= 1, j++; + for(int a = 2; a <= min((ll)37, n-1); a++) { + ll v = pow_mod(a, d, n); + if(v == 1 || v == n-1) continue; + for(int i = 1; i <= j; i++) { + v = mult_mod(v, v, n); + if(v == n-1 || v <= 1) break; + } + + if(v != n-1) return false; + } + return true; +} -- cgit v1.2.3