筛法求素数，求详解！谢谢。用c语言实现。。

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#includeusing 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<以上两种算法在小数据下速度几乎相同。