求素数的几种方法
什么是素数？
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。
方法（1）
由此定义可以得出求素数的第一种方法，也是最基本的方法，设要判断的数为M，就是把2到它本身M的数都遍历一遍，在遍历的过程中发现如果又被它整除的数，就记录这个数n，判断M是否和N相等，若M==N，就说明该数是素数。
#include<iostream>
using namespace std;
int function(int &m)
{
int i,j;
for(i=2;i<=m;i++)
{
if(m%i==0)
{j=i;break;}
}
if(j==m)
return 1;
else
return 0;
}
int main()
{
int k,m;
cout<<"please input m"<<endl;
cin>>m;
k=function(m);
if(k==0)
cout<<m<<"is not a sushu!"<<endl;
else
cout<<m<<"is a sushu!"<<endl;
return 0;
}
方法（2）
由于方法（1）采用的方法是从二开始它本身遍历的，这种方式遍历的太多，按照数分奇数、偶数的原则，可以把遍历的数过滤一半，过滤的原则就是先对一个数进行奇偶判断，若是奇数，只对从3到它本身的奇数进行求余运算，同理若是偶数，一定不是素数。
#include<iostream>
using namespace std;
int function(int &m)
{
int i,j=1;
if(m%2==0)
return 0;
else
for(i=3;i<=m;i=i+2)
{
if(m%i==0)
{j=i;break;}
}
if(j==m)
return 1;
else
return 0;
}
int main()
{
int k,m;
cout<<"please input m"<<endl;
cin>>m;
k=function(m);
if(k==0)
cout<<m<<" is not a sushu!"<<endl;
else
cout<<m<<" is a sushu!"<<endl;
return 0;
}
方法（3）
方法（2）采用的遍历的方式，遍历的是从二开始的它本身的奇数，这种遍历的方式遍历的数据还是有点多，其实要想判断一个数是否是素数，只需要判断到该数的一半即可，在方法（2）的基础上，遍历的数据量大大减少。这种方法采用的原理很简单，对该数进行判断是素数的过程中，如果超过它本身的一半，进行求余的结果永远不会为0，除非是该数对该数求余。
#include<iostream>
#include<cmath>
using namespace std;
int function(int &m)
{
int i;
if(m % 2 == 0)
return 0;
for( i=3;i<=m/2;i+=2)
if(m % i == 0)
return 0;
return 1;
}
int main()
{
int k,m;
cout<<"please input m"<<endl;
cin>>m;
k=function(m);
if(k==0)
cout<<m<<" is not a sushu!"<<endl;
else
cout<<m<<" is a sushu!"<<endl;
return 0;
}
方法(4)
采用方法（3）进行筛选的数据量还是很大，为了是数据的筛选量减少，还可以采用将被判断数m，进行开方作为判断结束的条件。因为开平方后的数是M的最大因子，最大因子之后的数对判断该数是否是素数没有意义。
#include<iostream>
#include<cmath>
using namespace std;
int function(int &m)
{
int i;
if(m % 2 == 0)
return 0;
for( i=3;i<=sqrt(m);i+=2)
if(m % i == 0)
return 0;
return 1;
}
int main()
{
int k,m;
cout<<"please input m"<<endl;
cin>>m;
k=function(m);
if(k==0)
cout<<m<<"is not a sushu!"<<endl;
else
cout<<m<<"is a sushu!"<<endl;
return 0;
}
补充：综合编程 , 其他综合 ,
