www百科

  1. 首页 > 生活知识 >

c语言求素数的代码 c语言求素数( 二 )

生活百科



极致优化

筛法的复杂度已经非常近似O(n)了，因为即使在n很大的时候，经过两次ln的计算，也非常近似常数了，实际上在绝大多数使用场景当中，上面的算法已经足够应用了 。
但是仍然有大牛不知满足，继续对算法做出了优化，将其优化到了O(n)的复杂度 。虽然从效率上来看并没有数量级的提升，但是应用到的思想非常巧妙，值得我们学习 。在我们理解这个优化之前，先来看看之前的筛法还有什么可以优化的地方 。比较明显地可以看出来，对于一个合数而言，它可能会被多个素数筛去 。比如38，它有2和19这两个素因数，那么它就会被置为两次False，这就带来了额外的开销，如果对于每一个合数我们只更新一次，那么是不是就能优化到O(n)了呢？
怎么样保证每个合数只被更新一次呢？这里要用到一个定理，就是每个合数分解质因数只有的结果是唯一的 。既然是唯一的，那么一定可以找到最小的质因数，如果我们能够保证一个合数只会被它最小的质因数更新为False，那么整个优化就完成了 。
那我们具体怎么做呢？其实也不难，我们假设整数n的最小质因数是m，那么我们用小于m的素数i乘上n可以得到一个合数 。我们将这个合数消除，对于这个合数而言，i一定是它最小的质因数 。因为它等于i * n，n最小的质因数是m，i 又小于m，所以i是它最小的质因数，我们用这样的方法来生成消除的合数，这样来保证每个合数只会被它最小的质因数消除 。
根据这一点，我们可以写出新的代码：
def ertosthenes(n):primes = <>is_prime = * (n+1)for i in range(2, n+1):if is_prime:primes.append(i)for j, p in enumerate(primes):# 防止越界if p > n // i:break# 过滤is_prime = False# 当i % p等于0的时候说明p就是i最小的质因数if i % p == 0:breakreturn primes
总结

到这里，我们关于埃式筛法的介绍就告一段落了 。埃式筛法的优化版本相对来说要难以记忆一些，如果记不住的话，可以就只使用优化之前的版本，两者的效率相差并不大，完全在可以接受的范围之内 。
筛法看着代码非常简单，但是非常重要，有了它，我们就可以在短时间内获得大量的素数，快速地获得一个素数表 。有了素数表之后，很多问题就简单许多了，比如因数分解的问题，比如信息加密的问题等等 。我每次回顾筛法算法的时候都会忍不住感慨，这个两千多年前被发明出来的算法至今看来非但不过时，仍然还是那么巧妙 。希望大家都能怀着崇敬的心情，理解算法当中的精髓 。
如果喜欢本文，可以的话，请点个关注，给我一点鼓励，也方便获取更多文章 。
【c语言求素数的代码 c语言求素数】本文始发于：公众号TechFlow

推荐阅读


上一篇：楚乔的结局是什么意思

下一篇：4000795522是哪家电话