主要因素为300亿？

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

Answer 1

您还记得在找到它们时按每个因素划分您正在分解的数字吗？

比如说,你发现2是一个因素.您可以将其添加到因子列表中,然后将您尝试分解的数字除以该值.

现在你只是在寻找1500亿的因素.每次你应该从你刚刚找到的因素开始.因此,如果2是一个因素,再次测试2.如果您找到的下一个因素是3,则再次从2进行测试无法进行测试.

等等...

Answer 2

使用蛮力很难找到素因子,这听起来像你正在使用的技术.

以下是一些提高速度的技巧:

• 开始低,不高
• 不要费心测试每个潜在因素,看看它是否是素数 - 只测试LIKELY素数(奇数以1,3,7或9结尾)
• 不要打扰测试偶数(可以被2整除),或者以5结尾的几率(全部可以被5整除).当然,实际上不要跳过2和5 !!
• 当您找到一个主要因素时,请务必将其分开 - 不要继续使用您的大量原始号码.请参阅下面的示例.
• 如果您找到一个因子,请务必再次测试它以查看它是否在那里多次.你的号码可能是2x2x3x7x7x7x31或类似的东西.
• 达到> = sqrt时停止(剩余大数)

编辑:一个简单的例子:您正在找到275的因子.

1. 测试275的可除性为2. 275/2 = int(275/2)？没有.失败.
2. 测试275的可分性为3.失败.
3. 跳过4!
4. 通过5测试275的可分性.是的!275/5 = 55.所以你的新测试号现在是55.
5. 通过5 测试55的可分性.是的!55/5 = 11.所以你的新测试号现在是11.
6. 但是5> sqrt(11),所以11是素数,你可以停下来!

所以275 = 5*5*11

更有意义吗？

Answer 3

保理大数字是一个难题.事实上,我们很难依靠它来保持RSA的安全.但是,请查看维基百科页面,了解可以提供帮助的算法的一些指示.但对于一个小的数字,它真的不应该花那么长时间,除非你一遍又一遍地重新做一些你不需要去的地方.

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

• 特别检查2,然后只检查奇数.
• 你只需要检查数字的平方根(如果你找不到因素,那么数字是素数).
• 找到因子后,不要使用原始数字来查找下一个因子,除以找到的因子,然后搜索新的较小数字.
• 当你找到一个因子时,尽可能多地划分它.之后,您再也不需要检查该号码或任何较小的号码.
• 如果您执行以上所有操作,您找到的每个新因子都将成为素数,因为已经删除了任何较小的因子.

Answer 4

这是一个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()使用费马的小定理,以便确定原理是有效的.