求素数的几种方法

《求素数的几种方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求素数的几种方法什么是素数？质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。方法（1）由此定义可以得出求素数的第一种方法，也是最基本的方法，设要判断的数为M，就是把2到它本身M的数都遍历一遍，在遍历的过程中发现如果又被它整除的数，就记录这个数n，判断M是否和N相等，若M==N，就说明该数是素数。#includeusingnamespacestd;intfunction(int&m){inti,j;for(i=2;i<=m;i++){if(m%i==0){j=i;break

2、;}}if(j==m)return1;elsereturn0;}intmain(){intk,m;cout<<"pleaseinputm"<>m;k=function(m);if(k==0)cout<

3、它本身的奇数进行求余运算，同理若是偶数，一定不是素数。#includeusingnamespacestd;intfunction(int&m){inti,j=1;if(m%2==0)return0;elsefor(i=3;i<=m;i=i+2){if(m%i==0){j=i;break;}}if(j==m)return1;elsereturn0;}intmain(){intk,m;cout<<"pleaseinputm"<>m;k=function(m);if(k==0)cout<

4、isnotasushu!"<#includeusingna

5、mespacestd;intfunction(int&m){inti;if(m%2==0)return0;for(i=3;i<=m/2;i+=2)if(m%i==0)return0;return1;}intmain(){intk,m;cout<<"pleaseinputm"<>m;k=function(m);if(k==0)cout<

6、为了是数据的筛选量减少，还可以采用将被判断数m，进行开方作为判断结束的条件。因为开平方后的数是M的最大因子，最大因子之后的数对判断该数是否是素数没有意义。#include#includeusingnamespacestd;intfunction(int&m){inti;if(m%2==0)return0;for(i=3;i<=sqrt(m);i+=2)if(m%i==0)return0;return1;}intmain(){intk,m;cout<<"pleaseinputm"<

7、>>m;k=function(m);if(k==0)cout<