厄拉多塞素数筛选法

素数，即为只能被1和它本身整除的正整数，其中1不为正整数，素数又称质数。

从2开始累加，同时对2进行标记素数，然后把2的其他倍数都去掉（或者标记为非素数），然后找到下一个没有标记的数，将其标记为素数，同时把它的其他倍数都去掉（或者标记为非素数）。如此反复，知道标记完所有的数，这样便找出了所有的素数。

LeetCode示例

计数质数

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

代码：

int countPrimes(int n) {
    int size=0;
    vector<bool> prime(n,false);
    for(int i=2;i<n;i++)
    {
        if(prime[i])
            continue;
        size++; 
        /**
       * 厄拉多塞筛选法
      */
        for(int j=i+i;j<n;j+=i)
        {
            prime[j] = true;
        }
    }
    return size;
}

【3】用6N±1法求素数。

任何一个自然数，总可以表示成为如下的形式之一：
6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数。所以，除了2和3之外，所有的素数都可以表示成6N±1的形式(N为自然数)。
根据上述分析，我们可以构造另一面筛子，只对形如6 N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度。

参考：

https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-bao-li-fa-ji-you-hua-shai-fa-ji-you/

厄拉多塞素数筛选法

原文：https://www.cnblogs.com/xiao--ge/p/12993963.html