From 0545e74aeab679ff67e95b62f788a79d6a31f222 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sun, 14 Feb 2016 00:36:49 +0100 Subject: Adding Jojo's Miller-Rabin code to the document and improving prime sieve. --- math/miller_rabin.cpp | 20 -------------------- 1 file changed, 20 deletions(-) delete mode 100644 math/miller_rabin.cpp (limited to 'math/miller_rabin.cpp') diff --git a/math/miller_rabin.cpp b/math/miller_rabin.cpp deleted file mode 100644 index ad8c163..0000000 --- a/math/miller_rabin.cpp +++ /dev/null @@ -1,20 +0,0 @@ -//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