a monte carlo primer

#include <iostream>

#include <ctime>

#include <cstdlib>

using namespace std;

void power(unsigned int a,unsigned int p,unsigned int n,unsigned int &result,bool &composite)

{

    //对n的二次探测

    unsigned int x;

    if(p==0)

    result=1;

    else

    {

        power(a,p/2,n,x,composite);

        result=(x*x)%n;

        if((result==1)&&(x!=1)&&(x!=n-1))

        composite=true;

        if((p%2)==1)

        result=(result*a)%n;

    }

}//求a的p次方模n 

//判定素数的motecarlo算法

bool Prime(unsigned int n)

{

    unsigned int a,result;srand(time(0));

    bool composite=false;

    a=rand()%(n-3)+2;

    power(a,n-1,n,result,composite);

    if(composite||(result!=1))return false;

    else return true;

}