algorithm - 300 000 000 000 的质因数？

Question

我需要找出超过 3000 亿的质因数。我有一个功能正在添加到它们的列表中......非常缓慢！它现在已经运行了大约一个小时，我认为它还有很长的路要走。我这样做是完全错误的还是预期的？

编辑：我试图找到数字 600851475143 的最大素数。

编辑：结果：

{
    List<Int64> ListOfPrimeFactors = new List<Int64>();
    Int64 Number = 600851475143;
    Int64 DividingNumber = 2;

    while (DividingNumber < Number / DividingNumber)
    {
        if (Number % DividingNumber == 0)
        {
            ListOfPrimeFactors.Add(DividingNumber);
            Number = Number/DividingNumber;
        }
        else
            DividingNumber++;
        }
        ListOfPrimeFactors.Add(Number);
        listBox1.DataSource = ListOfPrimeFactors;
    }
}

score 25 · Accepted Answer

您是否记得在找到它们时将要分解的数字除以每个因子？

例如，假设您发现 2 是一个因子。您可以将其添加到您的因子列表中，然后您将尝试分解的数字除以该值。

现在你只搜索 1500 亿的因数。每次你都应该从你刚刚找到的因素开始。因此，如果 2 是一个因素，请再次测试 2。如果您找到的下一个因素是 3，那么再次从 2 进行测试是没有意义的。

等等...

score 20 · Accepted Answer

使用蛮力很难找到主要因素，这听起来像您正在使用的技术。

以下是一些加快速度的技巧：

起点低，不高
不要费心测试每个潜在因素以查看它是否是素数——只需测试 LIKELY 素数（以 1、3、7 或 9 结尾的奇数）
不要费心测试偶数（都可以被 2 整除）或以 5 结尾的赔率（都可以被 5 整除）。当然，实际上不要跳过 2 和 5！
当你找到一个质因数时，一定要把它分开——不要继续使用你的大量原始数字。请参阅下面的示例。
如果您发现某个因素，请确保再次对其进行测试，以查看它是否存在多次。你的号码可能是 2x2x3x7x7x7x31 或类似的东西。
到达 >= sqrt（剩余大数）时停止

编辑：一个简单的例子：您正在寻找 275 的因数。

测试 275 是否可被 2 整除。275/2 = int(275/2) 吗？不，失败。
测试 275 的可被 3 整除。失败。
跳过4！
测试 275 可被 5 整除。是的！275/5 = 55。所以你的新测试号现在是 55。
测试55是否能被 5 整除。是的！55/5 = 11。所以你的新测试号现在是 11。
但是 5 > sqrt (11)，所以 11 是素数，你可以停下来！

所以 275 = 5 * 5 * 11

更有意义？

score 17 · Accepted Answer

分解大数字是一个难题。事实上，这太难了，以至于我们依靠它来保证 RSA 的安全。但是请查看wikipedia 页面，了解一些可以提供帮助的算法指针。但是对于这么小的数字，它真的不应该花那么长时间，除非你一遍又一遍地重新做你不必去某个地方的工作。

对于蛮力解决方案，请记住您可以进行一些小型优化：

专门检查2，然后只检查奇数。
您只需要检查数字的平方根（如果到那时您没有找到任何因子，那么该数字是素数）。
一旦你找到了一个因子，不要使用原来的数字来寻找下一个因子，将它除以找到的因子，然后搜索新的更小的数字。
当你找到一个因素时，尽可能多地划分它。之后，您再也不需要检查该数字或任何较小的数字。
如果您执行上述所有操作，您找到的每个新因子都将是素数，因为任何较小的因子都已被删除。

score 10 · Accepted Answer

这是一个 XSLT 解决方案！

此 XSLT 转换需要 0.109 秒。

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:saxon="http://saxon.sf.net/"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="xs saxon f"
 >
 <xsl:import href="../f/func-Primes.xsl"/>

 <xsl:output method="text"/>


 <xsl:template name="initial" match="/*">
   <xsl:sequence select="f:maxPrimeFactor(600851475143)"/>
 </xsl:template>

 <xsl:function name="f:maxPrimeFactor" as="xs:integer">
   <xsl:param name="pNum" as="xs:integer"/>

   <xsl:sequence select=
    "if(f:isPrime($pNum))
       then $pNum
       else
         for $vEnd in xs:integer(floor(f:sqrt($pNum, 0.1E0))),
             $vDiv1 in (2 to $vEnd)[$pNum mod . = 0][1],
             $vDiv2 in $pNum idiv $vDiv1
           return 
             max((f:maxPrimeFactor($vDiv1),f:maxPrimeFactor($vDiv2)))
    "/>
 </xsl:function>
</xsl:stylesheet>

此转换仅在 0.109 秒内产生正确的结果（最大素因子 600851475143）。：

6857

转换使用f:sqrt()和f:isPrime()定义在XSLTFXSL 2.0中的函数式编程库。它本身完全用XSLT编写。FXSL

f:isPrime()使用费马小定理，因此确定素性是有效的。

score 3 · Accepted Answer

最后一件事没有人提到，也许是因为它看起来很明显。每次你找到一个因素并把它分开时，继续尝试这个因素，直到它失败。

64 只有一个质因数，2。如果你一直把 2 分开，直到你不能再用，你会发现它非常微不足道。

score 2 · Accepted Answer

$ time factor 300000000000 > /dev/null

real        0m0.027s
user        0m0.000s
sys         0m0.001s

如果需要一个小时，你就做错了。你甚至可能在某处有一个无限循环——确保你没有使用 32 位整数。

score 2 · Accepted Answer

理解为什么平方根很重要的关键是，考虑到在 n的平方根之下的每个 n 因子在它之上都有一个对应的因子。要看到这一点，请考虑如果 x 是 n 的因数，则 x/n = m，这意味着 x/m = n，因此 m 也是一个因数。

score 1 · Accepted Answer

我根本不认为它需要很长时间 - 这不是一个特别大的数字。

您能给我们一个导致您的代码困难的示例编号吗？

score 1 · Accepted Answer

这是给你们的一些 Haskell 优点:)

primeFactors n = factor n primes
  where factor n (p:ps) | p*p > n = [n]
                        | n `mod` p /= 0 = factor n ps
                        | otherwise = p : factor (n `div` p) (p:ps)
        primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

花了大约 0.5 秒才找到它们，所以我称之为成功。

score 1 · Accepted Answer

这是您可以获得答案的一个站点：Factoris - 在线分解服务。它可以处理非常大的数字，但它也可以分解代数表达式。

score 1 · Accepted Answer

最快的算法是筛算法，并且基于离散数学的神秘领域（至少在我头上），实现和测试复杂。

最简单的因式分解算法可能是（正如其他人所说）埃拉托色尼筛法。关于使用它来分解数字要记住的事情N：

总体思路：您正在检查可能的整数因子的递增序列，x以查看它们是否均分您的候选数N（在 C/Java/Javascript 中检查是否N % x == 0），在这种情况下 N 不是素数。
你只需要上升到sqrt(N)，但实际上并不计算sqrt(N): 只要你的测试因子 x 通过测试就循环x*x<N
如果您有内存来保存一堆以前的素数，请仅将它们用作测试因子（如果素数 P 未通过测试，请不要保存它们，P*P > N_max因为您将永远不会再使用它们
即使您不保存以前的素数，对于可能的因素，x只需检查 2 和所有奇数。是的，它需要更长的时间，但对于合理大小的数字来说不会更长。素数计数函数及其近似值可以告诉您哪些数字是素数；这部分减少得非常缓慢。即使对于 2 ⁶⁴ = 大约 1.8x10 ¹⁹，大约每 43 个数字中有一个是素数（= 每 21.5 个奇数中有一个是素数）。对于数字小于 2 ⁶⁴的因数，这些因数x小于 2 ³²其中大约每 20 个数字中有一个是素数 = 每 10 个奇数中有一个是素数。因此，您必须测试 10 倍的数字，但循环应该更快一些，而且您不必乱七八糟地存储所有这些素数。

还有一些更老、更简单的筛选算法，它们稍微复杂一些，但仍然可以理解。请参阅Dixon 的、Shanks和Fermat 的因式分解算法。我曾经读过一篇关于其中一个的文章，不记得是哪一篇了，但它们都相当简单，并使用平方差的代数性质。

如果您只是测试一个数字是否N为素数，而您实际上并不关心因素本身，请使用概率素数测试。我认为米勒-拉宾是最标准的。

score 1 · Accepted Answer

我花了一些时间，因为它只是吸引了我。我不会在这里粘贴代码。如果您好奇，请参阅这个 factor.py gist 。

请注意，在阅读此问题之前，我对因式分解一无所知（仍然不知道）。这只是上面BradC答案的 Python 实现。

在我的 MacBook 上，需要 0.002 秒来计算问题中提到的数字（600851475143）。

显然必须有很多更快的方法来做到这一点。我的程序需要 19 秒来计算 6008514751431331 的因子。但Factoris服务很快就会给出答案。

score 1 · Accepted Answer

具体号码是300425737571？它微不足道地考虑到 131 * 151 * 673 * 22567。我看不出有什么大惊小怪的......

score 0 · Accepted Answer

您可以使用Eratosthenes 的筛子找到素数，看看您的数是否可以被您找到的数整除。

score 0 · Accepted Answer

您只需要检查它的余数 mod(n) 其中 n 是素数 <= sqrt(N) 其中 N 是您要考虑的数字。即使在非常慢的计算机或 TI-85 上，它也不应该超过一个小时。

score 0 · Accepted Answer

您的算法必须是 FUBAR。在我使用 Python 编写的 1.6 GHz 上网本上，这只需要大约 0.1 秒。Python 并不以其惊人的速度而闻名。但是，它确实具有任意精度整数...

import math
import operator

def factor(n):
    """Given the number n, to factor yield a it's prime factors.
    factor(1) yields one result: 1. Negative n is not supported."""
    M = math.sqrt(n)  # no factors larger than M
    p = 2             # candidate factor to test
    while p <= M:     # keep looking until pointless
        d, m = divmod(n, p)
        if m == 0:
            yield p   # p is a prime factor
            n = d     # divide n accordingly
            M = math.sqrt(n)  # and adjust M
        else:
            p += 1    # p didn't pan out, try the next candidate
    yield n  # whatever's left in n is a prime factor

def test_factor(n):
    f = factor(n)
    n2 = reduce(operator.mul, f)
    assert n2 == n

def example():
    n = 600851475143
    f = list(factor(n))
    assert reduce(operator.mul, f) == n
    print n, "=", "*".join(str(p) for p in f)

example()

# output:
# 600851475143 = 71*839*1471*6857

（这段代码似乎无视我对数论的了解不足以填补顶针这一事实。）

score 0 · Accepted Answer

只是为了稍微扩展/改进“仅测试不以 5 结尾的奇数”的建议......

所有大于 3 的素数要么比 6 的倍数大一或小一（对于 x 的整数值，6x + 1 或 6x - 1）。

score -1 · Accepted Answer

即使使用相对幼稚的蛮力，也不应该花那么长时间。对于那个特定的数字，我可以在大约一秒钟内将其计入脑海。

您说您不想要解决方案（？），但这是您的“微妙”提示。该数字的唯一素数是最低的三个素数。

score -1 · Accepted Answer

这种大小的半素数用于加密，所以我很好奇你到底想用它们做什么。

除此之外，目前还没有好的方法可以在相对较短的时间内找到大数的素数分解。

algorithm - 300 000 000 000 的质因数？

19 回答 19

Related

Reference