正常的判断函数：
bool is_prime(int n)
{
int i;
if(n <= 1)
{
return false;
}
for(i=2;i*i<=n;i++)
{
if(n % i== 0)
{
return false;
}
}
return true;
}
输入一个数即可判断是否为素数。
省时间复杂度的Eratosthenes素数判断方法：
#include <iostream>
using namespace std;
const int maxnum=1000;
int main()
{
int i,j,c=0;
int prime[maxnum+1];
for(i=2;i<=maxnum;i++)
prime[i]=1;
for(i=2;i*i<=maxnum;i++)
{
if(prime[i]==1)
{
for(j=2*i;j<=maxnum;j++)
{
if(!prime[j])continue;
if(j%i==0)
prime[j]=0;
}
}
}
for(i=2;i<maxnum;i++)
{
if(prime[i])
{
cout<<i<<' ';
c++;
if(c%10==0)
cout<<endl;
}
}
cout<<"有"<<c<<"个素数！";
}
Eratosthenes素数判断方法可以更简便的求一定范围的素数。
看懂了这段代码大家会有很大的感触！
