求质数算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了求质数算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1525字，纯文字阅读大概需要3分钟。

内容图文

每天一个算法～求质数算法

import math
def sieve(size):    
     sieve= [True] * size    
     sieve[0] = False    
     sieve[1] = False    
     for i in range(2, int(math.sqrt(size)) + 1):       
          k= i * 2        
          while k < size:           
              sieve[k] = False           
              k += i    
              return sum(1 for x in sieve if x)
print(sieve(10000000000))

455052511

求解过程

方法1、递归函数

这是一个求质数个数的题不说了
简单做一个递归的优化，每次都用质数筛

@numba.jit()
def cur(size):
    sieve = [True] * size
    sieve[0] = False
    sieve[1] = False
    if size == 2:
        return sieve
    factor = [index for index, val in enumerate(cur(int(math.sqrt(size)+1))) if val]
    for i in factor:
        k = i * 2
        while k < size:
            sieve[k] = False
            k += i
    return sieve

def up(size):
    sieve = cur(size)
    return sum(1 for x in sieve if x)

关键在于@numba.jit()这一行，用了numba的及时解释器，把cur函数重新编译了。在我的mac上大概10分钟不到就可以出结果。很多数值计算在python 里面超级慢，但是用了numba的jit基本可以和c的效率同一数量级。并且写起来很方便，可以尽情地写for循环，方便jit理解，实际运行效率更高。用tensorflow写了神经网络顺便想用python简单处理一下数据，但是又被python的效率限制的童鞋可以尝试一下。我自己实测超级好用。（其实是我不会写c，233

方法2、暴力破解

https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-bao-li-fa-ji-you-hua-shai-fa-ji-you/
直接贴网址了，整体复制过来还要调整合适

方法3、死记硬背

我的智商有限，只能记四位数字，能者多劳，你们加油！！！

方法4、numba外挂加速

方法5、 掷骰子，看你的了

标签：,,,,,, 来源： https://blog.csdn.net/qq_42184753/article/details/115446055

内容总结

以上是互联网集市为您收集整理的求质数算法全部内容，希望文章能够帮你解决求质数算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---