summaryrefslogtreecommitdiff
path: root/math/rho.cpp
diff options
context:
space:
mode:
authorMZuenni <michi.zuendorf@gmail.com>2023-02-14 17:49:01 +0100
committerMZuenni <michi.zuendorf@gmail.com>2023-02-14 17:49:01 +0100
commite051a4ed9b70bb2363732d1c97f94746a08ed25b (patch)
tree34b840e612f725d87dd82e8ee9de205ca3ffd7e3 /math/rho.cpp
parent9a6aeb3f3fa1c5442ef99118b3b93ae47b2c43c4 (diff)
rearranged math
Diffstat (limited to 'math/rho.cpp')
-rw-r--r--math/rho.cpp5
1 files changed, 2 insertions, 3 deletions
diff --git a/math/rho.cpp b/math/rho.cpp
index 865a438..df70251 100644
--- a/math/rho.cpp
+++ b/math/rho.cpp
@@ -3,7 +3,7 @@ ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim.
if (n % 2 == 0) return 2;
ll x = 0, y = 0, prd = 2;
auto f = [n](lll x){return (x * x) % n + 1;};
- for (ll t = 30, i = n / 2 + 7; t % 40 || gcd(prd, n) == 1; t++) {
+ for (ll t = 30, i = n/2 + 7; t % 40 || gcd(prd, n) == 1; t++) {
if (x == y) x = ++i, y = f(x);
if (ll q = (lll)prd * abs(x-y) % n; q) prd = q;
x = f(x); y = f(f(y));
@@ -15,6 +15,5 @@ void factor(ll n, map<ll, int>& facts) {
if (n == 1) return;
if (isPrime(n)) {facts[n]++, return;}
ll f = rho(n);
- factor(n / f, facts);
- factor(f, facts);
+ factor(n / f, facts); factor(f, facts);
}