算法分享01——埃拉托斯特尼算法（埃氏筛）【简单】

这篇文章介绍了算法分享01——埃拉托斯特尼算法（埃氏筛）【简单】，分享给大家做个参考，收藏极客资料网收获更多编程知识

算法应用场景

高效记录素数（包括其数量）的相关问题

核心思想

筛除合数，留下素数：
若 x 是素数，那么 x 的倍数一定不是素数，那么这些数就可以直接排除，不必后续再次逐一遍历来降低效率。

既然要记录 x 的倍数都不为素数，显然我们在进行筛除之前就要创建一个容器来保存所有数（指要求范围的所有数）是否为素数的状态。

那么我们就通过一个数组 isPrime[] 来实现，如果数 i 为素数，那么 isPrime[i] 则为 1 ，否则为 0 ；
然后我们便从小到大遍历，若数为素数，则将其倍数（不包括该素数本身）都标记为合数（即数组对应下标值设为 0）；
如此一来，我们遍历完后只要看数组值为 1 的就是素数，那么记录素数数量甚至输出所有素数等操作都将变得游刃有余了。

正确性说明

首先我们通过上述的基本思想我们可知这个算法就是把里面的合数挑出来标记为 0 ,那么其实在数组创建时我们就是先全都标记为 1 的，即先全认为是素数，然后通过算法所筛出的确定的素数再来跳出合数，标记为 0 ，故全程数组的数就是一直在从 1 变为 0 ，也就是开始说的从中挑出合数。那么这个方法就显然不会将质数标记成合数（即从这个方法的感觉中就可确定：质数不会轻易标记成合数，但合数可能不会被发现从而被当作素数）

而我们刚拿到这个方法时难免会感到一种不确定感：为什么我一定能够确定遍历到某个素数（即数组值为 1）时它一定就是素数呢？会不会它本是合数，只是之前的遍历操作中未将它发现，从而有了漏网之鱼呢？

我们现在来一探究竟：首先，这个方法一定不会将素数标记为合数。当我们从小到大遍历时，若数 x 是合数，那么根据合数的性质知 x 至少有一个素数因数（注意 1 不为素数），我们就记为 y ，那么从小到大遍历中我们会在 x 之前先遍历到 y ，那么在把 y 的倍数标记为合数的时候定然就会把 x 标记为了合数，因此不会出现漏网之鱼的合数未被标记，导致误成为素数的情况。

优化

当我们知道了它的正确性的成立原因道理，接下来的优化操作就容易理解了：

对于质数 x ，若按先前的方式从 2x 开始标记为合数其实是会有重复操作的，会不会这个 2x 在之前就已经被标记为了合数的呢？如果是，那我这次的操作岂不是白干了！？

那我们现在就得研究从什么时候开始标记既不会遗漏，也不会重叠：

其实从上一节中的合数 x 至少有一个素数因数 y 我们其实就能猜到：在 x*x 之前数都不需要标记，因为之前的数 k*x 其中 k 取值从 2 ~ x-1 中的 k 是小于 x 的，那么有两种情况：一是 k 为质数，那么在遍历到 k 时 k*x 一定会被标记为合数的；二是 k 不为质数，那么也是照前面说的一样， k 必有一个素数因数 y ，那 k*x 也必会有一个素数因数 y ，那显然在遍历到 y 时 k*x 一定就会被标记为合数的。
而 x*x 又是只有因数 x 和 1，所以其只能靠 x 来标记为合数，故从 x*x 开始标记既保证了之前的已经被标记，也保证了开始的 x*x 只能靠 x 标记，因此从 x*x 开始就是最优“起点”。

算法步骤

1. 初始化筛子：创建长度为 n + 1 的 bool 类型（int 也未尝不可）数组 isPrime[n + 1]，其中数组的索引就代表对应的数字，而数组的值则表明其对应数字是否为素数（比如 isPrime[11] = 1 就代表数字11为素数），然后数组初始时全为 true ，但注意要把下标 0、1 位置设置为 false （这两个数规定了不为素数）
2. 筛除合数：从 i = 2 遍历到 $\sqrt{n}$ ，若 isPrime[i] = true ，则把 i 的所有倍数记为 false 。当然优化后就是从 i*i 开始标记为 false 。
3. 结果提取：遍历结束后，值为 true 的索引即是 1 ~ n 之间的所有素数。

示例代码 （C++）

class Solution {
public:
    int Primes(int n) {
        if (n <= 2) return 0;
        if (n == 3) return 1;
        vector<bool> IsPrime(n, true);
        
        for(int i = 3; i * i < n; i += 2){
            if(IsPrime[i]){
                for(int j = i * i; j < n; j += i){
                    IsPrime[j] = false;
                }
            }
        }
// 此时容器内的所有数都筛选完了，接下来就可按照题意进行想要的操作
// 如果为了进一步高效，甚至可以在进行筛选的过程中同步进行一些操作，但一定要保证在操作时所操作的数字已经筛选过了
};

复杂度分析

• 时间复杂度： O(nloglogn)
• 空间复杂度： O(n)

参考题目

• leetcode 204.计数质数

文章来源:https://www.cnblogs.com/RuiiGao/p/19843249
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！