2

我正在尝试收集一些关于素数的统计数据，其中包括数 (prime-1)/2 的因子分布。我知道有统一选择的数字的因子大小的通用公式，但我还没有看到任何关于小于素数的因子的分布。

我编写了一个程序来迭代从 2^63 之后的第一个素数开始的素数，然后使用直到 2^32 的所有素数的试除法来分解 (素数 - 1)/2。但是，这非常慢，因为要迭代很多素数（和大量内存）。我将每个素数存储为一个字节（通过存储从一个素数到下一个素数的增量）。我还对最大 2^64 的数字使用 Miller-Rabin 素数检验的确定性变体，因此我可以轻松检测剩余值（成功除法后）何时为素数。

我已经尝试过使用 pollard-rho 和椭圆曲线分解的变体，但是很难在试除法和切换到这些更复杂的方法之间找到正确的平衡。另外我不确定我是否正确地实现了它们，因为有时它们似乎需要很长时间才能找到一个因素，并且基于它们的渐近行为，我希望它们对于这么小的数字会很快。

我还没有找到任何关于分解许多数字的信息（而不是试图分解一个），但似乎应该有一些方法可以利用这一点来加速任务。

非常感谢任何关于此问题的建议、替代方法的指针或其他指导。

编辑：我存储素数的方式是存储下一个素数的 8 位偏移量，隐含的第一个素数是 3。因此，在我的算法中，我有一个单独的除以 2 的检查，然后我开始一个循环：

factorCounts = collections.Counter()
while N % 2 == 0:
    factorCounts[2] += 1
    N //= 2
pp = 3
for gg in smallPrimeGaps:
    if pp*pp > N:
        break
    if N % pp == 0:
        while N % pp == 0:
            factorCounts[pp] += 1
            N //= pp
    pp += gg

此外，我使用轮筛来计算试除的素数，并使用基于多个素数的余数的算法来获得给定起点之后的下一个素数。

我使用以下内容来测试给定的数字是否为素数（现在将代码移植到 c++）：

bool IsPrime(uint64_t n)
{
    if(n < 341531)
        return MillerRabinMulti(n, {9345883071009581737ull});
    else if(n < 1050535501)
        return MillerRabinMulti(n, {336781006125ull, 9639812373923155ull});
    else if(n < 350269456337)
        return MillerRabinMulti(n, {4230279247111683200ull, 14694767155120705706ull, 1664113952636775035ull});
    else if(n < 55245642489451)
        return MillerRabinMulti(n, {2ull, 141889084524735ull, 1199124725622454117, 11096072698276303650});
    else if(n < 7999252175582851)
        return MillerRabinMulti(n, {2ull, 4130806001517ull, 149795463772692060ull, 186635894390467037ull, 3967304179347715805ull});
    else if(n < 585226005592931977)
        return MillerRabinMulti(n, {2ull, 123635709730000ull, 9233062284813009ull, 43835965440333360ull, 761179012939631437ull, 1263739024124850375ull});
    else
        return MillerRabinMulti(n, {2ull, 325ull, 9375ull, 28178ull, 450775ull, 9780504ull, 1795265022ull});
}
4

2 回答 2

3

我没有明确的答案，但我确实有一些观察和一些建议。

在 2^63 和 2^64 之间大约有 2*10^17 个素数，所以你编写的任何程序都会运行一段时间。

让我们谈谈对 2^63 到 2^64 范围内的数字的素性检验。任何通用测试都会做比您需要的更多的工作，因此您可以通过编写专用测试来加快速度。我建议对基数 2 和 3 进行强伪素数检验（如 Miller-Rabin 中的检验）。如果这些检验中的任何一个显示数字是合数，那么你就完成了。否则，在强伪素数表中查找以 2 和 3 为基数的数字（二分搜索）（让 Google 为您找到这些表）。两个强伪素数检验和查表肯定会比您当前执行的确定性米勒拉宾检验更快，后者可能使用六个或七个碱基。

对于因式分解，尝试除法到 1000，然后是 Brent-Rho，直到已知素因数的乘积超过被分解数的立方根，应该相当快，几毫秒。然后，如果剩余的辅因子是复合的，它必然只有两个因子，所以 SQUFOF 将是一个很好的分割它们的算法，比其他方法更快，因为所有的算术都是用小于平方根的数字完成的。因式分解，在您的情况下，这意味着分解可以使用 32 位算术而不是 64 位算术来完成，所以它应该很快。

一种更好的方法不是因式分解和素数测试，而是使用埃拉托色尼筛法的变体来分解大块数字。这仍然会很慢，因为有 2.03 亿个筛分小于 2^32 的素数，并且您需要处理分段筛的簿记，但考虑到您一次考虑大量数字，这可能是最好的方法你的任务。

我的博客上有上述所有内容的代码。

于 2016-10-19T13:41:18.983 回答
0

这就是我以后存储素数的方式：（我假设你想要数字的因子，而不仅仅是素数测试）。

复制自我的网站http://chemicaldevelopment.us/programming/2016/10/03/PGS.html

我假设你知道这部分的二进制数系统。如果不是，只需将 1 视为“是”，将 0 视为“否”。

因此，有很多算法可以生成前几个素数。我使用埃拉托色尼筛法来计算一个列表。

但是，如果我们将素数存储为一个数组，例如 [2, 3, 5, 7]，这将占用太多空间。具体有多少空间？

嗯，32 位整数最多可以存储 2^32 每个占用 4 个字节，因为每个字节是 8 位，并且 32 / 8 = 4

如果我们想将每个素数存储在 2,000,000,000 以下，我们必须存储超过 98,000,000,000。这会占用更多空间，并且在运行时比 bitset 慢，这将在下面解释。

这种方法会占用 98,000,000 个整数的空间（每个是 32 位，即 4 个字节），当我们在运行时检查时，我们需要检查数组中的每个整数，直到找到它，或者找到一个更大的数字比它。

例如，假设我给你一个小素数列表：[2, 3, 5, 7, 11, 13, 17, 19]。我问你 15 是不是素数。你怎么告诉我？

好吧，您将浏览列表并将每个列表与 15 个进行比较。

2 = 15？

3 = 15？

. . .

17 = 15？

在这一点上，你可以停下来，因为你已经通过了 15 的位置，所以你知道它不是素数。

现在，假设我们使用一个位列表来告诉你这个数字是否是素数。上面的列表如下所示：

001101010001010001010

这从 0 开始，一直到 19

1 表示索引是素数，所以从左数：0、1、2

001 101010001010001010

最后一个粗体数字是 1，表示 2 是素数。

在这种情况下，如果我让你检查 15 是否是素数，你不需要遍历列表中的所有数字；您需要做的就是跳到 0 。. . 15，并检查那个位。

对于内存使用，第一种方法使用 98000000 个整数，而这个方法可以在一个整数中存储 32 个数字（使用 1 和 0 的列表），所以我们需要 2000000000/32=62500000 个整数。

所以它使用的内存大约是第一种方法的 60%，而且使用起来要快得多。

我们将第二种方法的整数数组存储在一个文件中，然后在运行时将其读回。

这使用 250MB 的内存来存储前 2000000000 个素数的数据。

您可以通过轮筛进一步减少这种情况（就像您存储 (prime-1)/2 所做的那样）

我会更多地介绍轮筛。

通过存储 (prime - 1)/2，你得到了正确的结果，而 2 是一个特例。

您可以将其扩展到p#（前p个素数的乘积）

例如，您对数字k使用(1#)*k+1

您还可以使用线性方程组(n#)*k+L，其中L是小于n#和 1 的素数集合，不包括前n 个素数。

因此，您也可以只存储6*k+1和6*k+5的信息，甚至更多，因为L={1, 2, 3, 5}{2, 3}

这些方法应该可以让你了解它背后的一些方法。

您将需要某种方式来实现此位集，例如 32 位整数列表或字符串。

查看：https ://pypi.python.org/pypi/bitarray了解可能的抽象

于 2016-10-18T14:20:51.377 回答