爱华网for(int i=2;i<=sqtr(x);i++)if(x%i==0)
这个程序简单，容易理解，可是时间复杂度实在让人无法忍受，遇到一个int64的数据规模，根本不可能在１Ｓ内可以出解，现在介绍一种RP素数判断法,也叫MILLER-RABBIN测试,在一些书上都有介绍,可是介绍得太简单,害得我这个脑袋本来就不好使的人调了半天才搞定......MR测试(MILLER-RABBIN测试,以下简称MR)是基于费马小定理的一个测试:N是一个正整数,如果存在一个整数B(0<B<N),且B^(N-1) MODN=1,那么N可能是一个素数,如果不为1,那么一定不是一个素数,这个测试基于这点,用随机算法可以随机取S个数(S可以在20-50左右),如果都满足,那么判断它是一个素数.听起来很考RP,但是如果S在50左右,它是一个素数的概率大得可以近似处理为1,在实际运用中绝对可以信赖.这个程序的瓶颈在于求B^(N-1) MOD N的值,之前我有篇文章,介绍了这种快速取模的方法,完全可以满足需要了.下面把我的程序列在下面,仅供参考:#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#define randomize() srand((unsigned)time(NULL))
long long n;
bool bs;int p(long long x,long long y)
{
long long t;
if(y==1)return x;
else
{
t=p(x,y/2);
if(y%2==1)
returnt*t*x%n;
else
returnt*t%n;
}
}
void mafei(long long n)
{
randomize();
bs=false;
for(int i=1;i<=20;i++)
{
long longs=(rand()%(120-20))+20;
if(p(s,n-1)==1)
bs=true;
}
}
int main()
{
cin>>n;
mafei(n);
if(bs)
cout<<"Y"<<'n';
else
cout<<"N"<<'n';
}
