From e051a4ed9b70bb2363732d1c97f94746a08ed25b Mon Sep 17 00:00:00 2001 From: MZuenni Date: Tue, 14 Feb 2023 17:49:01 +0100 Subject: rearranged math --- math/millerRabin.cpp | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-) (limited to 'math/millerRabin.cpp') diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp index e9ac9ea..e4d2f6e 100644 --- a/math/millerRabin.cpp +++ b/math/millerRabin.cpp @@ -1,20 +1,19 @@ constexpr ll bases32[] = {2, 7, 61}; constexpr ll bases64[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; - bool isPrime(ll n) { - if(n < 2 || n % 2 == 0) return n == 2; + if (n < 2 || n % 2 == 0) return n == 2; ll d = n - 1, j = 0; - while(d % 2 == 0) d /= 2, j++; - for(ll a : bases64) { + while (d % 2 == 0) d /= 2, j++; + for (ll a : bases64) { if (a % n == 0) continue; ll v = powMod(a, d, n); //with mulmod or int128 - if(v == 1 || v == n - 1) continue; - for(ll i = 1; i <= j; i++) { + if (v == 1 || v == n - 1) continue; + for (ll i = 1; i <= j; i++) { v = (v * v) % n; //mulmod or int128 - if(v == n - 1 || v <= 1) break; + if (v == n - 1 || v <= 1) break; } - if(v != n - 1) return false; + if (v != n - 1) return false; } return true; } -- cgit v1.2.3