创建一个 pi(x) 表

pi(x)表示素数的个数<= x。例如，pi(100) = 25.我想创建一个表来存储所有x <= L的pi(x)值。我认为最快的方法是使用埃拉托色尼的筛子。首先，我标记所有素数，然后使用动态规划，对素数计数求和，并在每次出现新素数时增加。这是在下面的 Java 代码中实现的：

public static int [] piTableSimple (int L)
{
int sqrtl = (int) Math.sqrt(L);
int [] piTable = new int [L + 1];
Arrays.fill(piTable, 1);
piTable[0] = 0;
piTable[1] = 0;
for (int i = 2 ; i <= sqrtl ; i++)
if (piTable[i] == 1)
for (int j = i * i ; j <= L ; j += i)
piTable[j] = 0;
for (int i = 1 ; i < piTable.length ; i++)
piTable[i] += piTable[i - 1];
return piTable;
}

此实现存在 2 个问题：

它使用大量内存，因为空间复杂度O(n)
因为 Java 数组是"int"索引的，所以L的界限是2^31 - 1

不过我可以"作弊"一点。因为对于x的偶数值，pi(x) = pi(x - 1)，使我既可以将内存使用量减少 2 倍，又可以将L的界限增加 2 倍 (Lmax <= 2^32(。

这是通过对上述代码的简单修改来实现的：

public static long [] piTableSmart (long L)
{
long sqrtl = (long) Math.sqrt(L);
long [] piTable = new long [(int) (L/2 + 1)];
Arrays.fill(piTable, 1);
piTable[0] = 0;
piTable[1] = 0;
piTable[2] = 1;
for (int i = 3 ; i <= sqrtl ; i += 2)
if (piTable[(i + 1) / 2] == 1)
{
long li = (long) i;
long inc = li * 2L;
for (long j = li * li ; j <= L ; j += inc)
piTable[(int) ((j + 1) / 2)] = 0;
}
piTable[2] = 2;
for (int i = 1 ; i < piTable.length ; i++)
piTable[i] += piTable[i - 1];
return piTable;
}

请注意，pi(2) = 1的值不会在此数组中直接重新执行。但这有简单的解决方法和检查来解决它。这种实现的成本很小，pi(x)的实际值不是以直接的方式访问的，而是访问pi(x)的值，必须使用

piTable[(x + 1) / 2]

当然，这适用于x的偶数值和奇数值。后者在我相当慢的笔记本电脑上完成了在 10 秒内为x <= L = 10^9创建一个pi(x)表。

我想进一步减少所需的空间，并增加L的范围，而不会严重降低性能(例如，访问pi(x)值的算术运算的成本，如后一个代码中的值，几乎不会降低性能(。它能以高效和智能的方式完成吗？

你应该使用分段的埃拉托色尼筛，这将内存需求从O(n(减少到O(sqrt(n((。下面是一个实现。

你需要存储所有的圆周率吗？这是一个计算 pi(x( 的函数。它相当快到 10**12。

如果您觉得这有用，请对此答案以及两个链接的答案投赞成票。

现在我更了解你想做什么，我可以给出更好的答案。

计算pi(x(的正常方法从按间隔排列的预先计算的表开始，然后使用分段筛子在预先计算的点之间进行插值;预计算可以通过筛分或其他几种方法中的任何一种来完成。正如你所指出的，这些桌子变得很大。如果您希望能够计算高达 10 20 的 pi(x(，并且您愿意在每次有人调用您的函数时筛选最多 10¹²的范围，您将需要一个包含¹⁰^{8 个}64 位整数的表，这将占用近一 GB 的空间;对函数的调用每次筛选大约需要半分钟，假设是最近老式的个人计算机。当然，您可以通过选择将拥有多少预先计算的点来选择您想要在时间/空间权衡曲线上的位置。

您正在谈论计算x> 10²⁴的 pi(x(，这将占用更多空间或更多时间，或两者兼而有之。很多。最近计算了 pi(x( 的巨大值的项目，对于x的值，如 10²⁴或 10²⁵，需要几个月的时间来计算。

你可能想看看Kim Walisch的primesieve程序，它有一个非常快速的分段筛子。你也可以看看Tomás Oliveira e Silva的网站，在那里你可以找到pi(x(到10²²的表格。

说了这么多，你想做的事情可能不可行。

相关内容

最新更新

热门标签：