主要因素为300亿？

我需要找出超过3000亿的主要因素.我有一个功能,正在添加到他们的列表......非常慢!它现在已经运行了大约一个小时,我认为它还有一段距离可以走了.我这样做是完全错误还是预期？

编辑:我试图找到数字600851475143的最大素数因子.

编辑:结果:

{
    List ListOfPrimeFactors = new List();
    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;
    }
}

Alnitak.. 25

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

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

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

等等...

1> Alnitak..：

---

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

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

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

等等...

2> BradC..：

---

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

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

开始低,不高

不要费心测试每个潜在因素,看看它是否是素数 - 只测试LIKELY素数(奇数以1,3,7或9结尾)

不要打扰测试偶数(可以被2整除),或者以5结尾的几率(全部可以被5整除).当然,实际上不要跳过2和5 !!

当您找到一个主要因素时,请务必将其分开 - 不要继续使用您的大量原始号码.请参阅下面的示例.

如果您找到一个因子,请务必再次测试它以查看它是否在那里多次.你的号码可能是2x2x3x7x7x7x31或类似的东西.

达到> = sqrt时停止(剩余大数)

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

测试275的可除性为2. 275/2 = int(275/2)？没有.失败.

测试275的可分性为3.失败.

跳过4!

通过5测试275的可分性.是的!275/5 = 55.所以你的新测试号现在是55.

通过5 测试55的可分性.是的!55/5 = 11.所以你的新测试号现在是11.

但是5> sqrt(11),所以11是素数,你可以停下来!

所以275 = 5*5*11

更有意义吗？

3> Eclipse..：

---

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

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

特别检查2,然后只检查奇数.

你只需要检查数字的平方根(如果你找不到因素,那么数字是素数).

找到因子后,不要使用原始数字来查找下一个因子,除以找到的因子,然后搜索新的较小数字.

当你找到一个因子时,尽可能多地划分它.之后,您再也不需要检查该号码或任何较小的号码.

如果您执行以上所有操作,您找到的每个新因子都将成为素数,因为已经删除了任何较小的因子.

4> Dimitre Nova..：

---

这是一个XSLT解决方案!

此XSLT转换需要0.109秒.

此转换仅在0.109秒内产生正确的结果(最大素数因子600851475143).:

6857

转换使用f:sqrt()和f:isPrime()定义的FXSL 2.0- 一个用于XSLT中的函数编程的库.FXSL本身完全是用XSLT编写的.

f:isPrime()使用费马的小定理,以便确定原理是有效的.

---

方式整洁!太糟糕的问题3论坛已经关闭,所以你不能在那里发布.我不认为我在那里看过XSLT解决方案.

---

@PEZ:感谢您提及ProjectEuler.我已经解决了28个问题,我使用的唯一编程语言是XSLT.