1、算法一：令A为素数，则A*N（N>1;N为自然数）都不是素数。 #define range 2000bool IsPrime[range+1];//set函数确定i是否为素数，结果储存在IsPrime[i]中，此函数在DEV C++中测试通过void set(bool IsPrime[]){int i,j;for(i=0;i<=range;++i)IsPrime[i]=true;IsPrime[0]=IsPrime[1]=false;for(i=2;i<=range;++i){if(IsPrime[i]){for(j=2*i;j<=range;j+=i)IsPrime[j]=false;}}}2、
说明：解决这个问题的诀窍是如何安排删除的次序，使得每一个非质数都只被删除一次。 中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。例如，16=2^4，18=2 * 3^2，691488=2^5 * 3^2 * 7^4等。如果把因式分解中最小质数写在最左边，有16=4^2，18=2*9,691488=2^5 * 21609,；换句话说，把合数N写成N=p^k * q，此时q当然是大于p的，因为p是因式分解中最小的质数。由于因式分解的唯一性，任何一个合数N，写成N=p^k * q;的方式也是唯一的。 由于q>=p的关系，因此在删除非质数时，如果已知p是质数，可以先删除p^2,p^3,p^4,... ，再删除pq,p^2*q,p^3*q,...,（q是比p大而没有被删除的数），一直到pq>N为止。
因为每个非质数都只被删除一次，可想而知，这个程序的速度一定相当快。依据Gries与Misra的文章，线性的时间，也就是与N成正比的时间就足够了（此时要找出2N的质数）。 （摘自《C语言名题精选百则（技巧篇）》，冼镜光 编著，机械工业出版社，2005年7月第一版第一次印刷）。代码如下： #include<iostream>#include<cmath>using namespace std;int main(){int N; cin>>N;int *Location=new int[N+1];for(int i=0;i!=N+1;++i)Location[i]=i;Location[1]=0; //筛除部分 int p,q,end;end=sqrt((double)N)+1;for(p=2;p!=end;++p){if(Location[p]){for(q=p;p*q<=N;++q){if(Location[q]){for(int k=p*q;k<=N;k*=p)Location[k]=0;}}}}int m=0;for(int i=1;i!=N+1;++i){if(Location[i]!=0){cout<<Location[i]<< ;++m;}if(m%10==0) cout<<endl;}cout<<endl<<m<<endl;return 0;} 该代码在Visual Studio 2010 环境下测试通过。
以上两种算法在小数据下速度几乎相同。
#include <cstring>
#define N 100000
int flag[N];
int prime[20000];
void init()
{
memset(flag,0,sizeof(flag)); //全部置为0
int q = 0; //prime数组的下标
int i;
for(i = 2;i * i < N;i++)
{
if(flag[i]) continue; //表示i为前面某个数的倍数，肯定不是素数
prime[q++] = i;
for(int j = i * i;j < N;j += i) //将是i倍数的全部筛掉
{
flag[j] = 1;
}
}
for(i;i <= N;i++) //从i统计到N便是求得的2——N内的素数
{
if(flag[i] == 0) prime[q++] = i;
}
for(i = 0;i < 25;i++) //打印前25个素数供你检查，就是100以内的那25个素数
{
printf("%d ",prime[i]);
}
printf("\n");
}
int main()
{
init();
return 0;
}本回答被网友采纳