本文共 1099 字，大约阅读时间需要 3 分钟。

埃拉托列尼赛算法

1. 算法描述:对于给定的数n；求在2~n之间的质数。
2. 算法过程：
   举例说明，求2~12的质数；
   第一次：2 3 4 5 6 7 8 9 10 11 12（开始用2除后面的，可以除尽的抹去）
   第二次：2 3 5 7 9 11 (开始用3除后面的，可以除尽的抹去）
   第三次: 2 3 5 7 11 (开始用5除后面的，可以除尽的抹去）
   第四次: 2 3 5 7 11 (开始用7除后面的，可以除尽的抹去）
   第五次: 2 3 5 7 11 (11后面没有数了，不再进行)
   第五次即为最后结果；但实际上我们发现其实第三次就不用往后面走了，原因如下:
   如果当前除数为p，那么他后面可以被他整除的只有p2，p3，…,但观察发现其实
   p2，p3，…,p*(p-1)为止，都是p以前的数检查过了，该抹去的也抹去了，因此从
   pp开始即可，那么当pp大于n时，就没必要在进行下去了，也就是说上面第三次时，
   其实5*5>12了，就应该停止了。
   相信你对该算法已经掌握了，下面上代码:(c++）

#include
   
    using namespace std;//埃拉脱色尼塞算法求质数struct Array{
      int exist;   int number;};Array a[100];void Find(int n){
       for (int i=1;i<=n;i++)    {
           a[i].exist=1;        a[i].number=i;    }    int i=2;//用来指示当前的倍数的下标    int t;    int j;    int number;    while(a[i].number*a[i].number<=n)    {
           for(j=i+1;j<=n;j++)        {
               if(a[j].exist==1&&a[j].number%a[i].number==0)                a[j].exist=0;        }        i++;        while(a[i].exist!=1)            i++;    }    for (int i=2;i<=n;i++)    {
           if(a[i].exist==1)            cout<
    
     <<" ";    }}int main(){
       Find(25);}
    
   

共同学习！

转载地址：http://xilzi.baihongyu.com/