我希望创建一个程序来实现n<=10^14的素数计数功能

我想不出比 Sieve of Eratosthenes 为了你想要的,所以我会这么做。

Eratosthenes筛只需要检查一个数的素数,直到该数的平方根,因此您不需要为 全部的 素数小于10^14-只有素数小于10^ 7。

有 664,579 primes 小于10^7-即使在规格非常适中的计算机上,这种大小的数组也应该很好(将它们存储为4字节整数,大约为2MB)。

下面是一个伪代码方法:

• 为小于10^7的素数创建存储空间,我们称之为除数存储。
• 在你的存储中播种第一粒种子2。
• 为找到的素数创建一个计数器,将其初始化为1(对于素数2)。
• 为主要候选人创建一个计数器,从3开始。
• 将候选素数除以除数存储器中的所有素数。如果没有余数,则它是素数,所以将其添加到除数存储中(除非它大于10^7),并递增素数计数器。
• 将候选计数器增加2。
• 重复最后两步,直到最佳候选人超过10^14。

在保持除数素数不变的情况下,你不需要这样做——你可以天真地除以每一个小于候选数根的数,但这会更快。

这是一种非常粗糙的方法,但它有效。