java - 创建 pi(x) 表

Question

让pi(x)表示素数的个数 <= x 。例如，pi(100) = 25 。我想创建一个存储 pi(x) 值的表对于所有人x <= L 。我认为最快的方法是使用埃拉托色尼筛。首先，我标记所有素数，然后使用动态规划，对素数计数求和，并在每次出现新素数时增加。这是在下面的 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;
    }

此实现有两个问题:

1. 它使用大量内存，因为空间复杂度为 O(n)

2. 因为 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 的偶数和奇数值当然。后者完成创建pi(x)表 x <= L = 10^9在我的速度相当慢的笔记本电脑上需要 10 秒。

我想进一步减少所需的空间并增加 L 的界限就我的目的而言，不会严重降低性能(例如，访问 pi(x) 的值时稍微多一点的算术运算的成本几乎不会降低性能)。能否以高效、智能的方式完成？

Answer 1

您应该使用分段埃拉托色尼筛法，这会将内存需求从 O(n) 减少到 O(sqrt(n))。这是一个implementation .

你需要存储所有的圆周率吗？这是function计算 pi(x)。达到 10**12 的速度相当快。

如果您觉得这有用，请投票支持该答案以及两个链接的答案。