求质数是有许许多多算法的,毕竟这也是一个比较久远的问题了。而目前求质数的算法在现在更多地要求高效,于是各种算法都发展起来了。。。。。。。。。。。。。。
首先,我们容易想到的是:从2开始遍历,然后求他是否有除自己和1之外的因子。。。
然后我们可能会想到从3开始只遍历奇数。。。。。。。。。。。。
再我们可能想到了从2遍历到当前测试数的根号2向下取整,这排除了比较多的不可能因子。。。
除了遍历的方法,我们也可以想到,将得到的质数放入一个质数数组中,然后直接遍历该质数数组来判断是否质数。。
当然遍历上限十分之大的时候,我们就需要一些新算法了。我就取其中的一个算法来试验,那就是Miller&Rabin算法:
这个算法的核心是一个质数定理:费马定理 : 若一个正整数n,满足(1~n-1)之内任意一个数a
.使得 (a^(n-1))%n=1,则n为素数。。
当然,光靠这个定理是很看计算机的性能的。所以就需要一点改良:
Rabin-Miller素数测试:
通过在n的a值范围内取一定量的随机数,若都满足费马定理。那么在一定的误差内判定n是一个素数。
他的优点是算法十分快速,缺点是有一定的误差。但是可以通过添加一些条件或者改变参数来减小误差。
********************************************下面是代码*****************************************************
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define COUNT 100 //COUNT即测试的次数
bool getModel(int a,int n){
int t=n-1;
int cause=a;
while(--t){
cause=(cause*a)%n;
}
return cause==1;
}
bool judge(int n){
if(n==2)return true;
if(n>=3&&n%2){
int a;
srand(time(0));//生成种子
for(int i=0;i<COUNT;i++){ //随机40次 费马定理检验:
a=static_cast<int>(n*rand()/(RAND_MAX+1));//随机取到a值
if(a==1||a==0)a=2;
return getModel(a,n);
}
return true;
}
return false;
}
int main(){
int num=1;
int GOON;
cin>>GOON;
while(GOON!=0){
int ceil=num+100;
for(num;num<ceil;num++){
if(judge(num)){
cout<<num<<"是一个质数。"<<endl;
}
}
cin>>GOON;
}
system("pause");
return 0;
}
好了,我们来看看效果怎么样吧(下面的图是从1到3000的质数用此算法算出来的,颜色代表误差)
由下可见COUNT=100时,1-3000的质数有10个误差,还算好,但是速度很快。不设置条件的话直接就到80000以上了····
误差可以通过一些条件的加强来判断,比如我将COUNT设置为2000.。。。。
速度几乎和100一样快...
相关推荐
round robin scheduling -a Survey.pdfround robin scheduling -a Survey.pdfround robin scheduling -a Survey.pdfround robin scheduling -a Survey.pdfround robin scheduling -a Survey.pdfround robin ...
创客的 nano 板子的原理图
Book Reviews 249 references to sex, supposedly the mule that drags adolescents from the ditch of childhood dependency into the freedom of adulthood. Lastly, only scant mention of the “identity ...
金融&金融科技行业周报:央行强调防范外部冲击,Robinhood冲刺美股.pdf
Verilog Round Robin Arbiter Model
20210704-平安证券-金融&金融科技行业周报:央行强调防范外部冲击,robinhood冲刺美股.pdf
J., & ROBIN, S. S. O L E A R Y , K. D., & O‘LEAnY, S. G. O’LEAKY, K . D., PELHAM, W. E., ROSENBAUM, A., & PRICE, G. H. PKINZ, R. J . , ROBERTS, W. A,, & HANTMAN, E. TRITES, R . L. WkiAi.tx...
J., & ROBIN, S. S. O L E A R Y , K. D., & O‘LEAnY, S. G. O’LEAKY, K . D., PELHAM, W. E., ROSENBAUM, A., & PRICE, G. H. PKINZ, R. J . , ROBERTS, W. A,, & HANTMAN, E. TRITES, R . L. WkiAi.tx...
MILLER-RABIN 素数测试算法课程报告 内含代码
基于linux C实现Robin调度算法
安信非银2021年第23期周报:基金销售持续火热,Robinhood登陆美股.pdf
关于MKS-Robin-Nano V1.x和V2.x Robin Nano V1.x和Robin Nano V2.x之间的区别如下: ——————————————————————————————————————————————————————————...
基于专家系统和Round-Robin算法的芯片编程系统.pdf
时间片轮转法:程序模拟进程的时间片轮转RR调度过程。Time slice Round-Robin: program to simulate the process time slice rotation RR scheduling process.
资源分类:Python库 所属语言:Python 资源全名:jc.robinhood-1.1.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
OpenGL初学者必看Nate Robin的OpenGL教程.zipOpenGL初学者必看Nate Robin的OpenGL教程.zipOpenGL初学者必看Nate Robin的OpenGL教程.zipOpenGL初学者必看Nate Robin的OpenGL教程.zipOpenGL初学者必看Nate Robin的...
带权重的优先级轮转算法的verilog实现
基于螺旋线的Round-Robin Crossbar调度算法
robinhood:用react.js克隆robinhood