#include"iostream.h"
#include"time.h"
#include"stdlib.h"
#include"math.h"
class judge_prime
{
private:
public:
int Btest(int a,int n);
int MillRab(int n);
int RepeatMillRab(int n,int k);
};
int judge_prime:: Btest(int a,int n)
{
int s=0;
int t=n-1;
int i=1;
int x=1;
int y;
do
{
s++;
t=t/2;
}while((t%2)!=1);
while(i<=t)
{
x=(x*a)%n;
i++;
}
if((x==1)||(x==n-1))return 1;
for(int j=1;j<=s-1;j++)
{
y=1;
for(int k=1;k<=j;k++)
{
y=2*y;
}
i=1;
x=1;
while(i<=(y*t))
{
x=(x*a)%n;
i++;
}
if(x==n-1)return 1;
}
return 0;
}
int judge_prime::MillRab(int n)
{
int a;
srand((unsigned)time(0));
a=rand()%(n-3)+2;
return Btest(a,n);
}
int judge_prime::RepeatMillRab(int n,int k)
{
int i;
for(i=1;i<=k;i++)
{
if(MillRab(n)==0)return 0;
}
return 1;
}
int main()
{
int i;
int n;
int count=0;
cout<<"Input n:";
cin>>n;
int result=0;
cout<<2<<" "<<3<<" ";
for(i=5;i<=n;)
{
judge_prime P;
if(P.RepeatMillRab(i,(int)log10(i)))
{ cout<<i<<" ";
count++;
if(count%10==0)
cout<<endl;}
i=i+2;
}
return 0;
}//具体的解释就不说了,全在上面的理论中.