分解质数rho

#include"iostream"
#include"time.h"
#include"vector"
#include"stdlib.h"
#include"string.h"
#include"map"
#include"cmath"
using namespace std;
const int cishu=10;
long long mul(long long a,long long b,long long mod)
{
    a%=mod;
    b%=mod;
    long long res=0,base=a;
    while(b)
    {
        if(b&1)res=(res+base)%mod;
        base=(base*2)%mod;
        b>>=1;
    }
    return res;
} 

long long ksm(long long a,long long b,long long mod)
{
    a%=mod;
    long long res=1,base=a;
    while(b)
    {
        if(b&1)res=mul(res,base,mod);
        base=mul(base,base,mod);
        b>>=1;
    }
    return res;
}
int check(long long a,long long d,int t,long long n)
{
    long long x=ksm(a,d,n);
    if(x==1||x==n-1)return 1;
    for(int i=1;i<=t;i++)
    {
        x=ksm(x,2,n);
        if(x==n-1)return 1;
    }
    return 0;
}
int Miller_Rabin(long long n)
{
    if(n==1)return 0;
    if(n==2)return 1;
    if(n==3)return 1;
    if((n&1)==0)return 0;
    if(n%3==0)return 0; 
    long long x=n;
    x--;
    int t=0;
    while((x&1)==0)
    {
        x>>=1;
        t++;
    }
    for(int ci=0;ci<cishu;ci++)
    {
        int a=(rand()-2)%x+2;
        if(check(a,x,t,n)==0)return 0;
    }
    return 1;

}
long long abss(long long n)
{
    if(n<0)return -n;
    else return n;
}
long long gcd(long long a,long long b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
}
long long rho(long long n ,long long c)
{
    long long x,y,d,i=1,k=2;
    x=(rand()%(n-1))+1;
    y=x;
    while(1)
    {
        i++;
        x=(mul(x,x,n)+c)%n;
        d=gcd(abss(y-x),n);
        if(d>1&&d<n)return d;
        if(x==y)return n;
        if(i==k)//Ö»Òª1 2 4 8 .... 
        {
            y=x;
            k<<=1;
        }
    }
}
map<long long ,int>mp;
void find(long long n)
{
    if(n==1)return ;
    if(Miller_Rabin(n))
    {
        mp[n]++;
        return ;
    }
    long long p=n;
    while(p>=n)p=rho(p,rand()%(n-1)+1);
    find(p);
    find(n/p);
}
long long N;
int main()
{
    while(cin>>N)
    {
        mp.clear();
        find(N);
        for(map<long long,int>::iterator i=mp.begin();i!=mp.end();i++)
        {
            cout<<i->first<<" "<<i->second<<"\n";
        }
    }
}