素数测试问题.cpp

王晓东算法设计与分析源码。vc下编译通过能够运行。且运行效率较高

#include<iostream>
#include<cstdlib>
using namespace std;
unsigned __int64 fMultiModular(unsigned __int64 a,unsigned __int64 b,const unsigned __int64 n)
{
	unsigned __int64 back = 0,temp = a%n;
	while(b>0)
	{
		if(b&0x1){
			if((back = back + temp)>n)
				back -= n;
		}
		if((temp <<=1)>n)
			temp -=n;
		b >>=1;
	}
	return back;
}
unsigned __int64 modular_exp(const unsigned __int64 a,unsigned __int64 b,const unsigned __int64 n)
{
	unsigned __int64 d = 1,dTemp = a%n;
	while(b>0)
	{
		if(b&0x1)
			d = fMultiModular(d,dTemp,n);
		dTemp = fMultiModular(dTemp,dTemp,n);
		b >>=1;
	}
	return d;
}
bool fWitNess(const unsigned __int64 a,const unsigned __int64 n,char t,const unsigned __int64 u)
{
	unsigned __int64 x,y;
	x = modular_exp(a,u,n);
	while(t--)
	{
		y = fMultiModular(x,x,n);
		if(y==1&&x!=1&&x!=n-1)
			return true;
		x = y;
	}
	return y!=1;
}
bool miller_rabin(const unsigned __int64 n,int count)
{
	if(n==1)
		return false;
	if(n==2)
		return true;
	unsigned __int64 a,u;
	char t = 0;
	for(u = n-1;!(u&0x1);u>>=1)
		++t;
	for(int i=1;i<=count;++i)
	{
		a = rand()%(n-1)+1;
		if(fWitNess(a,n,t,u))
			return false;
	}
	return true;
}
int main()
{
	unsigned __int64 test_num;
	while(scanf("%I64u",&test_num)==1)
	{
	//if(test_num==0){printf("NO\n");return 0;}
    	if(miller_rabin(test_num,20))
		      printf("YES\n");
	    else printf("NO\n");
    }
    //return 0;
	system("pause");
}