我想创建一个程序来实现 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)。
这是一种非常粗糙的方法，但它确实有效。
我可以使用埃拉托色尼筛法来计算素数的数量，但它需要我创建一个大到无法创建的数组。我只是期待找到一种方法或算法来完成任务。一个名称或引用可以达到目的。我只需要一些方法来完成任务。有了方法，我会弄清楚编程部分。请帮忙
我想不出比 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)。
这是一种非常粗糙的方法，但它确实有效。