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

I wish to create a program to implement prime-counting function for 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)并增加素数找到计数器。
  • 将候选计数器增加二。
  • 重复最后两步进入素数候选超过10^14.

您不需要保留除数素数 - 您可以天真地除以小于候选方根的每个数字,但这将更快地达到 log(n)。

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