当前位置：文江博客话题详情

algorithm prime-factoring fxsl

300 000 000 000 的质因数？

发布于 2024-07-11 09:02:37 字数 703 浏览 5 评论 0 原文

我需要找出超过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;
    }
}

原文

I need to find out the prime factors of over 300 billion. I have a function that is adding to the list of them...very slowly! It has been running for about an hour now and i think its got a fair distance to go still. Am i doing it completly wrong or is this expected?

Edit: Im trying to find the largest prime factor of the number 600851475143.

Edit:
Result:

{
    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;
    }
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

殤城〤 2024-07-18 09:02:38

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

回复收藏 0 原文

流年里的时光 2024-07-18 09:02:38

你的算法必须是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

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

Your algorithm must be FUBAR. This only takes about 0.1s on my 1.6 GHz netbook in Python. Python isn't known for its blazing speed. It does, however, have arbitrary precision integers...

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

(This code seems to work in defiance of the fact that I don't know enough about number theory to fill a thimble.)

回复收藏 0 原文

绝影如岚 2024-07-18 09:02:38

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

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

回复收藏 0 原文

猫烠⑼条掵仅有一顆心 2024-07-18 09:02:38

即使使用相对简单的蛮力，也不应该花那么长时间。对于这个具体数字，我可以在大约一秒钟的时间内在脑海中将其分解。

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

回复收藏 0 原文

我做我的改变 2024-07-18 09:02:38

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

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

回复收藏 0 原文

辞旧 2024-07-18 09:02:37

您是否记得将要因式分解的数字除以找到的每个因数？

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

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

等等...

回复收藏 0 原文

焚却相思 2024-07-18 09:02:37

使用蛮力查找素因数很困难，这听起来像是您正在使用的技术。

这里有一些加快速度的技巧：

从低开始，而不是从高开始
不要费心去测试每个潜在的因子来看看它是否是素数——只需测试类似的素数（以 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

更有意义吗？

回复收藏 0 原文

﹎☆浅夏丿初晴 2024-07-18 09:02:37

对大数进行因式分解是一个难题。事实上，如此困难以至于我们依赖它来保证 RSA 的安全。但请查看维基百科页面，了解一些可以提供帮助的算法指针。但对于这么小的数字，确实不应该花那么长时间，除非您一遍又一遍地重复工作，而不必在某个地方做。

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

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

回复收藏 0 原文

ぶ宁プ宁ぶ 2024-07-18 09:02:37

这是一个 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() 定义于 FXSL 2.0 —— XSLT。 FXSL 本身完全是用 XSLT。

f:isPrime() 使用< strong>费马小定理，从而可以高效地确定素性。

Here is an XSLT solution!

This XSLT transformation takes 0.109 sec.

<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>

This transformation produces the correct result (the maximum prime factor of 600851475143) in just 0.109 sec.:

6857

The transformation uses the f:sqrt() and f:isPrime() defined in FXSL 2.0 -- a library for functional programming in XSLT. FXSL is itself written entirely in XSLT.

f:isPrime() uses Fermat's little theorem so that it is efficient to determine primeality.

回复收藏 0 原文

心房敞 2024-07-18 09:02:37

最后一件事没有人提到，也许是因为它看起来很明显。每次找到一个因子并将其除掉时，不断尝试该因子，直到失败为止。

64 只有一个质因数 2。如果你不断地除 2 直到你不能除为止，你会发现这个结果非常微不足道。

回复收藏 0 原文

再见回来 2024-07-18 09:02:37

$ time factor 300000000000 > /dev/null

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

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

$ time factor 300000000000 > /dev/null

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

You're doing something wrong if it's taking an hour. You might even have an infinite loop somewhere - make sure you're not using 32-bit ints.

回复收藏 0 原文

归途 2024-07-18 09:02:37

理解平方根为何如此重要的关键在于，考虑到 n 的每个因子低于 n 的平方根都有一个对应的因子高于。要了解这一点，请考虑如果 x 是 n 的因子，则 x/n = m，这意味着 x/m = n，因此 m 也是一个因子。

回复收藏 0 原文

梦屿孤独相伴 2024-07-18 09:02:37

我根本不认为它会花费很长时间——这并不是一个特别大的数字。

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

回复收藏 0 原文

笑看君怀她人 2024-07-18 09:02:37

您可以在以下网站上获得答案：Factoris - 在线分解服务。它可以计算非常大的数字，但它也可以分解代数表达式。

回复收藏 0 原文

温柔一刀 2024-07-18 09:02:37

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

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

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

还有一些较旧且更简单的筛选算法，它们稍微复杂一些，但仍然相当容易理解。请参阅迪克森，Shanks' 和费马的< /a> 因式分解算法。我读过一篇关于其中一篇的文章，不记得是哪一篇了，但它们都相当简单，并且使用平方差的代数性质。

如果您只是测试数字 N 是否是素数，并且实际上并不关心因子本身，请使用概率素性测试。我认为 Miller-Rabin 是最标准的。

The fastest algorithms are sieve algorithms, and are based on arcane areas of discrete mathematics (over my head at least), complicated to implement and test.

The simplest algorithm for factoring is probably (as others have said) the Sieve of Eratosthenes. Things to remember about using this to factor a number N:

general idea: you're checking an increasing sequence of possible integer factors x to see if they evenly divide your candidate number N (in C/Java/Javascript check whether N % x == 0) in which case N is not prime.
you just need to go up to sqrt(N), but don't actually calculate sqrt(N): loop as long as your test factor x passes the test x*x<N
if you have the memory to save a bunch of previous primes, use only those as the test factors (and don't save them if prime P fails the test P*P > N_max since you'll never use them again
Even if you don't save the previous primes, for possible factors x just check 2 and all the odd numbers. Yes, it will take longer, but not that much longer for reasonable sized numbers. The prime-counting function and its approximations can tell you what fraction of numbers are prime; this fraction decreases very slowly. Even for 2⁶⁴ = approx 1.8x10¹⁹, roughly one out of every 43 numbers is prime (= one out of every 21.5 odd numbers is prime). For factors of numbers less than 2⁶⁴, those factors x are less than 2³² where about one out of every 20 numbers is prime = one out of every 10 odd numbers is prime. So you'll have to test 10 times as many numbers, but the loop should be a bit faster and you don't have to mess around with storing all those primes.

There are also some older and simpler sieve algorithms that a little bit more complex but still fairly understandable. See Dixon's, Shanks' and Fermat's factoring algorithms. I read an article about one of these once, can't remember which one, but they're all fairly straightforward and use algebraic properties of the differences of squares.

If you're just testing whether a number N is prime, and you don't actually care about the factors themselves, use a probabilistic primality test. Miller-Rabin is the most standard one, I think.

回复收藏 0 原文

一页 2024-07-18 09:02:37

我花了一些时间在这上面，因为它让我着迷。我暂时不会将代码粘贴到这里。如果您好奇的话，请参阅this Factors.py gist。

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

在我的 MacBook 上，需要 0.002 秒来分解问题中提到的数字 (600851475143)。

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

回复收藏 0 原文

紫轩蝶泪 2024-07-18 09:02:37

具体号码是300425737571？它很简单地分解为 131 * 151 * 673 * 22567。
我不明白有什么大惊小怪的...

回复收藏 0 原文

柠檬色的秋千 2024-07-18 09:02:37

这里有一些 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 秒找到它们，所以我认为这是成功的。

Here's some Haskell goodness for you guys :)

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..]

Took it about .5 seconds to find them, so I'd call that a success.

回复收藏 0 原文