python - 计算素数列表中数字位置的最佳方法？

Question

例如

f(2)->1
f(3)->2
f(4)->-1 //4 is not a prime
f(5)->3
...

一般来说，做一个质数生成器，在它到达x之前计数

def f(x):
    p = primeGenerator()
    count=1
    while True:
        y = next(p)
        if y>x:
            return -1
        elif y==x:
            return count
        else:
            count+=1

是不是太慢了？虽然我可以为下一次调用缓存列表，如果我保证输入必须是素数，那么不必测试输入数字是否是素数，有没有更快的公式得到答案？

Answer 1

最佳方法取决于您获得的输入，以及该函数将被调用多次还是仅一次或几次。

如果它会经常被调用，并且你要接收的所有输入都是小的，不大于 10⁷ 比如说，最好的方法是提前创建一个查找表，然后看增加输入。

如果不经常调用，而且所有的输入都很小，只生成不超过输入的素数并计数就足够了。记住下一次调用已有的内容可能是一种增强，这样当第一个参数是 19394489，下一个是 20889937 时，您不需要再次从 0 开始，而只需要找到之间的质数他们。但是否值得拥有额外的存储空间取决于传递的参数。

如果会经常调用，而且参数不是太大，不超过10¹³的话，最好的方法是预先计算π(n)的值对于 n 的一些选择值，并为每个参数查找下一个较小的预计算点的值，然后生成并计算该点和目标值之间的素数(或者如果目标更接近到下一个更大的预计算点，计算目标和那个之间的素数)。

如果您计算例如π(n) 对于所有不超过 10¹³ 的 10⁷ 的倍数，您会得到一个包含一百万个条目的查找表，这不是很费力在现在的内存中，永远不需要筛选大于 500 万的范围，这不会花费很长时间。

您还可以将查找表作为磁盘上的文件或数据库，这样可以缩短预计算点之间的间隔。这也将消除在启动时读取预先计算的表的时间，但查找现在将涉及对文件系统的访问，这比内存读取花费的时间长得多。什么是最佳策略取决于预期的输入及其运行的系统。

如果上限不小，计算查找表将花费相当长的时间，但这是一次性成本。

如果预期的输入较大，例如最多 10¹⁶，并且您不愿意花费必要的时间来预先计算该范围的查找表，那么最好的办法是实现一个素数计数函数的更好算法，Meissel's method as refined by Lehmer实现起来相对容易(虽然不是那么容易，但我会在这里给出一个示例实现，但是 here's a Haskell implementation 可能会有所帮助)。更好，但更复杂的是 Miller et al 改进的方法.

除此之外，您还需要研究当前最先进的技术，并且可能应该使用比 Python 更底层的语言。