poj 1881:素因子分解+素数テスト

とても良い入門問題
まず素数であるかどうかをテストし,そうでなければ素因子分解を行い,アルゴリズムの詳細はmiller robinとpollard rhoアルゴリズムをまとめる
ACコード

#include <iostream>

#include<stdio.h>

#include<algorithm>

#include<math.h>

using namespace std;

long long ans;

long long gcd(long long a,long long b)

{

    return b?gcd(b,a%b):a;

}

long long random(long long n)

{

    return (long long)(rand()%(n-1)+1);

}

long long multi(long long a,long long b,long long m)//a*b%m

{

    long long res=0;

    while(b>0)

    {

        if(b&1)

            res=(res+a)%m;

        b>>=1;

        a=(a<<1)%m;

    }

    return res;

}

long long quickmod(long long a,long long b,long long m) //a^b%m

{

    long long res=1;

    while(b>0)

    {

        if(b&1)

            res=multi(res,a,m);

        b>>=1;

        a=multi(a,a,m);

    }

    return res;

}

int check(long long a,long long n,long long x,long long t)

{

    long long res=quickmod(a,x,n);

    long long last=res;

    for(int i=1;i<=t;i++)

    {

        res=multi(res,res,n);

        if(res==1&&last!=1&&last!=n-1) return 1;

        last=res;

    }

    if(res!=1) return 1;

    return 0;

}



int primetest(long long n)

{

    if(n<2)return 0;

    if(n==2)return 1;

    if((n&1)==0) return 0;

    long long x=n-1;

    long long t=0;

    while((x&1)==0){x>>=1;t++;}

    for(int i=0;i<20;i++)

    {

        long long a=random(n);

        if(check(a,n,x,t))

            return 0;

    }

    return 1;

}





long long pollardrho(long long n,long long c)

{

    long long x,y,d,i,k;

    i=1;k=2;

    x=random(n);

    y=x;

    while(1)

    {

        i++;

        x=(multi(x,x,n)+c)%n;

        long long tmp=y-x>=0?y-x:x-y;

        d=gcd(tmp,n);

        if(d>1&&d<n)

            return d;

        if(y==x)

            return n;

        if(i==k)

        {

            y=x;

            k+=k;

        }

    }

}

void findfac(long long n)

{

    if(n==1)

        return;

    if(primetest(n))

    {

        ans=min(ans,n);

        return;

    }

    long long p=n;

    while(p>=n)

        p=pollardrho(n,random(n-1));

    findfac(p);

    findfac(n/p);

}

int main()

{

    int t;

    long long n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%I64d",&n);

        if(primetest(n))

        {

            puts("Prime");

            continue;

        }

        ans=n;

        findfac(n);

        printf("%I64d
",ans);

    }

    return 0;

}