MonteCarlo算法+改进的Fermat判定素数方法

/*
 * Abstract：
 *         PPT147,EX10. MonteCarlo算法素数测定与确定性算法求素数的比较，
 *         并给出100~10000以内的错误的比例。 
 *
 * Author : Ace.Ma
 * Date   : 2012/9/28
 * Version: 0.1 
 */
#include<iostream>
#include<ctime>
#include<set>
#include<cmath>
using namespace std;

//该函数是素数测定的关键 
bool Btest(int a, int n)
{
	int s = 0;
	int t = n-1;
    unsigned long long x = 1;
	do{
		++s;
		t=t/2;
	}while( t%2 !=1 );
	for(int i=0;i<t;++i)
		x=(x*a)%n;
	if (x == 1 || x == n-1)
		return true;
	for (int i=1; i<=s-1; ++i)
	{
		x = (x*x) % n;
		if (x == n-1)
			return true;
	}
	return false;
}

bool MillRob(int n)
{
	int a = rand()%(n-3) + 2;
	return Btest(a,n);
}
/*
	判定n是不是素数
	k一般等于10，可以使错误的概率<百万分之一
*/
bool RepeatMillRob(int n, int k)
{
	for (int i=0; i<k; ++i)
	{
		if (MillRob(n) == false)
			return false;
	}
	return true;
}
/*
确定性算法，判断n是否为素数，若是返回true，否返回false。
*/
bool IsPrime(int n)
{
	for (int j=2; j<= (int) sqrt((double)n); ++j)
	{
		if ( n%j == 0)
		{
			return false;
		}
	}
	return true;
}


int main()
{
    int wrong = 0;
    int total = 0;
	
	for ( int n=101; n<=10001; n+=2)
	{
        if( IsPrime(n))
        {
            ++total;
            if ( !RepeatMillRob(n, (int)log((double)n)) )
            {
                 ++wrong;
            }
        } 
   }
   cout<<"total primes num:"<<total<<", wrong num:"<<wrong<<", wrong rate:"<<wrong/(double)total<<endl;
	system("pause");
	return 0;
    
} 

错误的比率为0，说明改进的Fermat测试素数很有效