Pollard - Rho (PTTNST)

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
long long Rand(long long l, long long r)
{
    return l + (abs(rd() *1LL * rd()) % (r - l + 1));
}
vector<int> Prime = {2, 3, 5, 7, 11, 13, 17, 23};
map<long long, int> Element;
long long Mul(long long a, long long b, long long mod)
{
    a %= mod;
    b %= mod;
    long long q = (long double)a * b/mod;
    long long r = a * b - q * mod;
    return (r % mod + mod) % mod;
}
long long Pow(long long a, long long b, long long mod)
{
    if (b == 0)
    {
        return 1 % mod;
    }
    long long t = Pow(a, b/2, mod);
    if (b & 1)
    {
        return Mul(Mul(t, t, mod), a, mod);
    }
    else
    {
        return Mul(t, t, mod);
    }
}
pair<long long, long long> factor(long long n)
{
    long long s = 0;
    while((n & 1) == 0)
    {
        n >>= 1;
        ++s;
    }
    return {s, n};
}
bool Test(long long s, long long d, long long n, long long witness)
{
    if (n == witness)
    {
        return true;
    }
    long long p = Pow(witness, d, n);
    if (p == 1)
    {
        return true;
    }
    for (; s > 0; -- s)
    {
        if (p == n - 1)
        {
            return true;
        }
        p = Mul(p, p, n);
    }
    return false;
}
void FastFact(long long n)
{
    long long p = 2;
    while (p * p <= n)
    {
        if (n % p == 0)
        {
            while (n % p == 0)
            {
                n /= p;
                ++Element[p];
            }
        }
        ++p;
    }
    if (n != 1)
    {
        ++Element[n];
    }
}
bool MillerRabin(long long n)
{
    if (n < 2)
    {
        return false;
    }
    if ((n & 1) == 0)
    {
        return n == 2;
    }
    long long s, d;
    tie(s, d) = factor(n - 1);
    for (int i : Prime)
    {
        if (!Test(s, d, n, i))
        {
            return false;
        }
    }
    return true;
}
long long f(long long x, long long mod)
{
    return (x * x + 1) % mod;
}
long long FindFactor(long long n)
{
    long long x = Rand(2, n);
    long long y = x, p = 1;
    do
    {
        x = f(x, n);
        y = f(f(y, n), n);
        p = __gcd( abs(x - y), n);
    }
    while (p == 1);
    return p;
}
void PollardRho(long long n)
{
    if (n == 1)
    {
        return ;
    }
    if (n <= 10000)
    {
        FastFact(n);
        return ;
    }
    if (MillerRabin(n))
    {
        ++Element[n];
        return ;
    }
    long long p = 0;
    while(p == 0 || p == n)
    {
        p = FindFactor(n);
        PollardRho(p);
        PollardRho(n/p);
    }
}
void read()
{
    long long n;
    cin >> n;
    PollardRho(n);
}
void solve()
{
    for (auto it : Element)
    {
        cout << it.first << ' '<< it.second << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen(TASK".INP", "r", stdin);
    //freopen(TASK".OUT", "w", stdout);
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        cerr << "Case " << __ << ":" << '\n';
        read();
        solve();
    }
}