找质数算法之埃拉托色尼筛选法（Sieve of Eratosthenes算法）

客官°小女子只卖身不卖艺 2022-09-23 03:49 172阅读 0赞

**一、算法原理**

一个合数总是可以分解成若干个质数的乘积，那么如果把质数（最初只知道2是质数）的倍数都去掉，那么剩下的就是质数了。

**二、步骤**

（1）先把1删除（1既不是质数也不是合数）

（2）读取队列中当前最小的数2，然后把2的倍数删去

（3）读取队列中当前最小的数3，然后把3的倍数删去

（4）读取队列中当前最小的数5，然后把5的倍数删去

.......

（n）读取队列中当前最小的状态为true的数n，然后把n的倍数删去

![20160703235154990][]

**三、实现**

**问题**：给一个数n，求出比n小的所有的质数有多少个

**思路**：用一个bool数组，存储n个数的状态，初始化都为true，然后从2开始，如果2的状态为true，就开始遍历比n小的所有的2的倍数，将其全部置为false。把2的倍数遍历完后，继续往下找下一个状态为true的数，即3，遍历比n小的所有的3的倍数（按3\*3，3\*4，3\*5这样遍历，注意不需要从3\*2开始了）。.....最后剩下的状态为true的数全为质数。

**四、代码**

class Solution {
    public:
        int countPrimes(int n) {
            if(n<=1)  //小于等于1的都不是质数
                return 0;
            bool* a = new bool[n+1];
            for(int i=0; i<n; i++)
                a[i] = true;
            for(int i=2; i*i<n; i++){
                if(a[i] == true){
                  for(int j=i; i*j<n; j++){
                      a[i*j] = false;
                  }  
                }//if
            }//for
            int result =0;
            for(int i=2; i<n; i++){
                if(a[i])
                    result++;
            }//for
            return result;
        }
    };

[20160703235154990]: /images/20220721/2b0bd8e38caa478d8d540cc82fef1b93.png