关于素数求不超过n的素数素数的判定-电脑资料VIP专享

关于素数：求不超过 n 的素数，素数的判定(MillerRabin 测试)-电脑资料关于素数的基本介绍请参考百度百科 here 和维基百科 here 的介 绍首先介绍几条关于素数的基本定理：定理 1：假如 n 不是素数，则 n 至少有一个(1,sqrt(n)]范围内 的的因子定理 2：假如 n 不是素数，则 n 至少有一个(1,sqrt(n)]范围内 的素数因子定理 3：定义 f(n)为不大于 n 的素数的个数，则 f(n)近似等于 n/ln(n)(ln 为自然对数)，具体请参考 here求不超过 n 的素数本文地址算法 1：埃拉托斯特尼筛法，该算法的核心思想是：首先标记 2~n的数都为素数，然后遍历 2~n 的数组，假如它是素数，就把它 的倍数标记为非素数(即把所有素数的倍数都标记为非素数)代码 如下：复制代码1unsignedintfindPrime(constunsignedintn,unsignedintprime [])2(3if(n<2)return0;4unsignedintprimeNum=0;5bool*isPrime=NULL;6//假如 n 太大，下面可能会申请内存失败8isPrime=newbool[n+1];//0 表示是素数，1 表示非素数9}catch(conststd::bad_alloc&e){10std::cout<<"bad_alloc:newfailed\n";11return-1;12}13memset(isPrime,0,sizeof(bool)*(n+1));14for(longlongi=2;i<=n;i++)15if(isPrime[i]==0)16{//所有素数的倍数都不是素数17prime[primeNum++]=i;18longlongt;19for(unsignedintk=2;(t=i*k)<=n;k++)20isPrime[t]=1;21}22delete[]isPrime;23returnprimeNum;//返回素数的个数24}复制代码算法 2：查表法，该算法主要根据定理 2,假如一个数是素数， 那么它不能被(1,sqrt(n)]范围内的素数整除，称之为查表法，主要 是因为当我们推断 n 是否为素数时，(1,sqrt(n)]范围内的素数已经 都计算出来了，可以利用已经计算出来的素数表，代码如下：复制代码1unsignedintfindPrime_table(constunsignedintn,unsignedin tprime[])2(3if(n<2)return0;4unsignedintprimeNum=0;5prime[primeNum++]=2;6for(longlongi=3;i<=n;i++)7(8unsignedinttmp=sqrt(i);9boolflag=true;10for(unsignedintj=0;prime[j]<=tmp;j++)11{12if(i%prime[j]==0)13{14flag=false;15break;16}17}18if(flag)19prime[primeNum++]=i;20}21returnprimeNum;//返回素数的个数22}复制代码对于两个算法的效率，我们分别计算不超过1,5,10,1,10,1,10 的素数，用时如下, 左边是算法 1 的耗时，右边是算法 2 的耗时，单位微妙（测试环境， win7x647G 内存，i5 处理器，codeblockwithgcc）...