博客介绍了MEISSEL-LEHMER算法，这是一种用于超高速计算素数个数的方法，能在百亿范围内实现3毫秒内的计算。尽管筛选法在一般情况下效率较高，但在ACM等对时间要求严格的场景下仍不足，而MEISSEL-LEHMER算法提供了解决这一问题的优化方案，使得计算速度大幅提升。
判断n以内素数个数有很多算法，最简单的是循环直接判断，这个效率不用说，n稍大就不行了。最流行的是筛选法，原理就是定义一个素数标志位表，初始为1，遇到一个数如果对应标志位为1判断这个数是不是素数，是将该为置1，不是放0，然后将他的倍数位置全部置0，然后继续。。这个效率还是比较快的，但是计算到10^8时候需要3s左右了，对于一般要求基本够了，但是对于ACM里面对时间要求很严还是不够。可以对帅选法进行优化，不如偶数直接跳过，以后直接加偶数倍，甚至加入移位运算判断是不是3的倍数，5的倍数等等，最后基本勉强在ACM要求的时间之内。下来介绍一种逆天的算法：MEISSEL-LEHMER，布吉岛的可以百度下。不容易看懂。。。。。。
先看下效果绝对碉堡！！！！
代码如下：
#
订阅专栏 解锁全文
扫一扫
1720
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
