algorithm - 给定一个数字 X，估计该数字可能落在素数有序列表中的哪个位置

Question

给定预先计算的有序素数列表和提供的数字 X，我想粗略估计 X 在素数列表中的位置，并从该点开始搜索。

因此，我计算了一个从 1..2^32-1 开始的素数列表并将其存储在一个二进制文件中。我在一个针对该文件运行的程序中有一些方法可以给我第 n 个素数、一个随机素数、存在多少个素数等等。但是为了向这个程序添加一个函数来告诉我提供的数字在哪里是素数，我无法想出一种方法来估计从哪里开始搜索。简单的 O(n) 方法很快变得不可行，即使对于 < 2^32 的数字也是如此。

我已经尝试了素数定理 (x/ln x)，并在其他一些领域进行了研究，但还没有完全找到正确的分布，恐怕我的数论达不到标准.

我正在寻找类似的东西，例如

1 2 3 4  5  6 .. 100 ..  500 .. 1000 ..  5000 ..  10000
2 3 5 7 11 13 .. 541 .. 3571 .. 7919 .. 48611 .. 104729

所以，lookup(13) 会给我一个接近的数字，但是 <= 6，lookup(7920) 会给我一个 <= 1000 的数字，而 lookup(104729) 会给我一个 <= 10000 的数字，等等。

附言我意识到这是一个愚蠢的方法有几个原因:a)我可以用不同的方式存储它并进行 O(1) 查找； b) 我可以大幅压缩存储空间； c) 对于这么小的数字，我可以在运行时对给定的数字进行质数测试，完全跳过查找表，这样会更快。我对这些问题的解决方案不感兴趣；我真的很想知道是否有一种行之有效的方法来估计给定数字可能落在排序的素数列表中的位置。因此，这更像是一个数学/数论问题，而不是一个实现问题。

附言这不是家庭作业。

P.P.P.S.我在 StackOverflow 上进行了非常彻底的搜索，但可能错过了对此的直接回答。

谢谢。

Answer 1

小于x的素数个数近似为x的对数积分，li(x)。反转函数*可以很好地估计第 k 个素数的大小。

如果你想避免编程对数积分，一个合理的近似值是

k ln n + k ln ln k - k

查看表中该点的值后，您可以通过该点的素数密度更准确地估计正确位置。因此，如果您想要第 100 万个素数并将其估计为 15,502,175，但发现此时最近的素数是第 1,001,000 个，您可以将第 100 万个素数重新估计为旧估计 - 1000 ln(15502175)。

* 从技术上讲，该函数不是双射的，因此不可逆，但很容易在您关心的区域上求逆，比如 x >= 2。