Untitled

mail@pastecode.io avatar
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();
}
Leave a Comment