Meissel-Lehmer算法 | caojiangxia
Opened this issue · 0 comments
caojiangxia commented
https://caojiangxia.github.io/Meissel-Lehmer/#more
Meissel-Lehmer算法这个算法是用来统计小于等于$n$的素数有多少个的算法。 算法来自于这篇论文，算法的细节，我并不清楚，在这里也只是mark一下这个算法，有空的时候再来研究，算法的时间复杂度是$O(n^{\frac 2 3})$。其实现的代码如下，扩大$N$可以计算到1e12级别： 1234567891011121314151617181920212223242526272829303