Untitled

unknown
plain_text
22 days ago
2.0 kB
2
Indexable
Never
//--this-template-is-from-cp-algorithms-------
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define fi first
#define se second

typedef long long ll;

using u64 = uint64_t;
using u128 = __uint128_t;

long long mult(ll a, ll b, ll mod) {
return (__int128)a * b % mod;
}

long long f(ll x, ll c, ll mod) {
return (mult(x, x, mod) + c) % mod;
}

u64 binpower(u64 base, u64 e, u64 mod) {
u64 result = 1;
base %= mod;
while (e) {
if (e & 1)
result = (u128)result * base % mod;
base = (u128)base * base % mod;
e >>= 1;
}
return result;
}

bool check_composite(u64 n, u64 a, u64 d, int s) {
u64 x = binpower(a, d, n);
if (x == 1 || x == n - 1)
return false;
for (int r = 1; r < s; r++) {
x = (u128)x * x % n;
if (x == n - 1)
return false;
}
return true;
};

bool MillerRabin(u64 n) { // returns true if n is prime, else returns false.
if (n < 2)
return false;

int r = 0;
u64 d = n - 1;
while ((d & 1) == 0) {
d >>= 1;
r++;
}

for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n == a)
return true;
if (check_composite(n, a, d, r))
return false;
}
return true;
}
ll rho(ll n) {
if(MillerRabin(n)) return n;
if(n == 1) return 1;
if(n % 2 == 0) return 2;
srand(time(NULL));
ll x = (rand() % (n - 2)) + 2;
ll y = x;
ll c = (rand() % (n - 1)) + 1;
ll g = 1;
while (g == 1) {
x = f(x, c, n);
y = f(y, c, n);
y = f(y, c, n);
g = __gcd(abs(x - y), n);
if(g == n) rho(n);
}
if(MillerRabin(g)) return g;
else return rho(g);
}
void Solve(){
ll n;
cin>>n;
vector<ll> res;
while(n > 1){
ll k = rho(n);
res.push_back(k);
n /= k;
}
sort(res.begin(), res.end());
for(auto x: res)
cout<<x<<nl;

}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
Solve();
}