I am trying to create a fast prime generator in Java. It is (more or less) accepted that the fastest way for this is the segmented sieve of Eratosthenes: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. Lots of optimizations can be further implemented to make it faster. As of now, my implementation generates 50847534 primes below 10^9 in about 1.6 seconds, but I am looking to make it faster and at least break the 1 second barrier. To increase the chance of getting good …
以清晰易懂的方式重新发布它，没有任何无法正确显示的复杂 MathJax：
\n\n我出于兴趣探索了一些计算机科学/数论挑战网站，他们提出了以下问题，具体如下：
\n\n让P(n) = sum{1<=k<=n} \xcf\x86(k)
寻找P(10^16)
我对此进行了相当长的搜索并尝试了不同的方法：
\n\n使用 的公式\xcf\x86(n)= n * product{1<=i<=k} (Pi-1)/Pi，我尝试计算\xcf\x86(n)范围内，但这对于大型 来说变得非常低效n。我可以通过这种方法得到尽可能多的结果10^7。除此之外，它就变得太慢了。
我尝试了另一种，更直接。维基百科和 Wolfram Alpha 建议使用类似的公式直接计算P(n)：
P(n) = sum {1<=k<=n} \xcf\x86(k)= 0.5\xe2\x8b\x85(1+\xe2\x88\x91{1<=k<=n} \xce\xbc(k)\xe2\x8b\x85\xe2\x8c\x8an/k\xe2\x8c\x8b^2)
这个公式看起来更有希望。我尝试了一下，虽然离目标还很远，10^7但距离目标还很远。通过预先计算莫比斯函数的筛子，我可以得到略小于 的值10^9。我的内存不足，无法计算筛子中的更多值。而且即使可以，也需要很长的时间，而且还很遥远10^16。
以下是我用 Java 编写的第二种方法的部分代码：
\n\npublic static BigInteger PhiSummatoryFunction (long limit)\n{\n BigInteger sum = BigInteger.ZERO;\n int [] m = MoebiusSieve(limit);\n for (int i=1;i<m.length;i++)\n …给定一组轴对齐的立方体S。任务是求出所有立方体的并n集体积S。这意味着 2 个或更多立方体的每个体积重叠仅计算一次。该集合具体包含所有立方体的所有坐标。
我找到了几篇有关该主题的论文，介绍了完成该任务的算法。例如，本文d将问题推广到任何维度而不是琐碎的维度d=3，并将问题推广到盒子而不是立方体。这篇论文以及其他一些论文及时O(n^1.5)或稍微好一点地解决了这个问题。另一篇看起来很有前途且专门针对的3d-cubes论文解决了以下任务：O(n^4/3 log n)。但这些论文看起来相当复杂，至少对我来说是这样，我无法清楚地理解它们。
是否有任何相对简单的伪代码或过程可以遵循来实现这个想法？我正在寻找一组说明，说明如何处理立方体。任何实施也将是优秀的。甚至O(n^2)都O(n^3)很好。
目前，我的方法是计算总体积，即所有立方体的所有体积之和，然后计算每两个立方体的重叠，并从总体积中减去它。问题是每个这样的重叠可能（或可能不是）属于不同的立方体对，这意味着重叠可以由 5 个立方体共享。在这种方法中，重叠将被计算 10 次，而不是仅计算一次。所以我想也许包含排除原则可能会证明自己有用，但我不知道它具体是如何实施的。（天真地）计算每个重叠已经是O(n^2)可行的。有没有更好的方法来计算所有这些重叠？无论如何，我不认为这是一个有用的方法，可以继续沿着这些思路继续下去。
我正在尝试实现一种方法，该方法将被赋予k序列的第一个整数值的数组。基于给定的值，该方法将检测是否可以使用整数系数的线性递归来生成序列的值。
C生成序列所需的整数系数的，大小的s <= k，具有s最小的越好。对于斐波那契数列，给定输入{0,1,1,2,3,5,13}，该方法将返回{1,1}。
对于 Tribonacci 序列，给定至少 3 个值的输入序列，该方法将返回 {1,1,1}
对于已知的递推关系f(n) = f(n - 1) + f(n - 2) - 3 * f(n - 5) + 4 * f(n - 10)，任何小于10值的输入序列都会返回错误，但给定一个至少包含10连续值的序列，该方法将返回{1,1,0,0,-3,0,0,0,0,4}对应于递推系数（i数组第 ' 个位置的零）表示f(n - i)不需要该值）。
显然，事先并不知道复发，只是为了简单起见，我给出了已知复发的例子。但是该方法需要自己检测它。
甚至可以做到吗？是否有任何已知的算法？我尝试用 Java 编写一些东西，但实际上它只不过是一种蛮力，检测所有可能的重复，这不是很有帮助......如果可能或任何点，我很想看到有效尝试的代码示例正确的方向。
编辑
经过一番搜索，我偶然发现了“Berlekamp-Massey 算法”，它似乎与这个主题有关。