2

例如

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

是不是太慢了？虽然我可以缓存下一次调用的列表，如果我保证输入必须是素数，所以不必测试输入数字是否是素数，是否有更快的公式来获取回答？

4

2 回答 2

3

最好的方法取决于你得到什么输入，以及函数是被调用多次还是只调用一次或几次。

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

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

如果经常调用它并且参数不是太大，例如不超过 10 13，最好的方法是预先计算 的π(n)某些选择值的值n，并为每个参数查找下一个较小的预先计算点的值，然后生成并计算该点与目标值之间的素数（或者如果目标更接近下一个更大的预计算点，则计算目标与该点之间的素数）。

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

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

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

如果预期的输入更大，例如最多 10 16，并且您不愿意花费必要的时间来预先计算该范围的查找表，那么您最好的选择是为素数计数函数实现更好的算法之一，由 Lehmer 改进的 Meissel 方法相对容易实现（虽然不是那么容易，我将在这里给出一个示例实现，但这里有一个 Haskell 实现可能会有所帮助）。更好，但更复杂的是米勒等人改进的方法。

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

于 2012-09-30T17:03:45.563 回答
2

您必须检查所有先前的候选人的素数。没有捷径。正如您所说，您可以缓存先前计算的结果并从那里开始，但这确实是您能做的最好的事情。

于 2012-09-30T00:20:25.110 回答