/**This won't work if the number is a big prime. So before running this algorithm check whether the number is a prime or not using Rabin Miller algorithm**/

//Pollard rho
//Copied from _Ash__

const long long LIM = LLONG_MAX;

long long mul(long long a, long long b, long long m){
    long long x, res;
    if (a < b) swap(a, b);
    if (!b) return 0;
    if (a < (LIM / b)) return ((a * b) % m);
    res = 0, x = (a % m);
    while (b){
        if (b & 1){
            res = res + x;
            if (res >= m) res -= m;
        }
        b >>= 1;
        x <<= 1;
        if (x >= m) x -= m;
    }
    return res;
}

long long pollard_rho(long long n, long long c) {
    long long x = 2, y = 2, i = 1, k = 2, d;
    while(true) {
        x = (mul(x, x, n) + c);
        if (x >= n) x -= n;
        d = __gcd(abs(x-y),n);
        if (d > 1) return d;
        if (++i == k) {
            y = x, k <<= 1;
        }
    }
    return n;
}

int main() {
    long long d = n;
    for(int i = 2; d == n; i++){
        d = pollard_rho(n, i);
    }
}