super_prime.cpp

快速求素数

#include <iostream.h>
#include<stdlib.h>
#include<time.h>
#include <math.h> 
#include <windows.h>  
#include <iomanip.h>

int uniform(int a,int b)  //生成a到b的随机小数
{

	int m = (a+(rand() % (b-a+1))) ;
	return m;
}

int ModularExponent(int a,int j,int p)//求方幂模s=a的j次方 mod p, 注意先求a的j次方可能会溢出
{
	int s=1;
	while(j>0)
	{
		if(j%2==1)
		{
			s=(s*a)%p;
		}
		a= a*a % p;
		j= j/2;
	}
	return s;
}

bool Btest(int a, int n)
{
	int s=0;
	int t=n-1;
	while( t%2==0 )
	{
		s++;
		t=t/2;
	}
	//int x=(int)pow(a,t)%n;
	int x=ModularExponent( a, t, 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 MillRab(int n)
{
	int a=uniform(2,n-2);
	return Btest(a,n);
}

bool repeatMillRab(int n,int k)
{
	for(int i=0;i<k;i++)
	{
		if(MillRab(n)==false)
		{	
			return false;
			break;
		}
	}
	return true;
}

int main()
{   
    int test;
	int k;
	int count=2;
	while(1)
	{
		cout<<"输入测试范围"<<endl;
		cin>>test;
		cout<<"输入循环精度"<<endl;
		cin>>k;
		cout<<setw(5)<<2 <<setw(5)<< 3;
		for(int i=2;i<=test/2;i++)
		{
			if(repeatMillRab(2*i+1,k))
			{
				cout<<setw(5)<<2*i+1;
		    	count++;
				if(count%10 ==0)
					cout<<endl ;
			}
		}
		cout<<endl;
		cout<<"共有"<<count<<endl;
	}
	return 0;

}

//结论：当循环精度为2时，此算法得到的质数为1231个，而确定性算法的结果为1229个
//      当循环精度为3时，次算法得到的质数为1229个，与确定性算法的结果相同，
//      当循环精度为4时，次算法得到的质数为1229个，与确定性算法的结果相同。