寻找主要因素

Question

#include <iostream>
using namespace std;

void whosprime(long long x)
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {
        for(int z = 2; z <= x; z++)
        {
            if((i != z) && (i%z == 0))
            {
                imPrime = false;
                break;
            }
        }

        if(imPrime && x%i == 0)
            cout << i << endl;

        imPrime = true;
    }    
}

int main()
{
    long long r = 600851475143LL;
    whosprime(r);  
}

我试图 在项目Euler上找到问题3指定的数字600851475143的素因子(它要求最高的素因子,但我想找到所有这些因素).但是,当我尝试运行此程序时,我没有得到任何结果.这与我的程序花费多长时间,甚至数字本身有什么关系？

另外,有哪些更有效的方法可以解决这个问题,你有什么建议可以解决这些更优雅的解决方案,因为我正在解决这个问题吗？

一如既往,谢谢!

Answer 1

你的算法错了; 你不需要我.这是通过试验分区进行整数分解的伪代码:

define factors(n)

    z = 2

    while (z * z <= n)

        if (n % z == 0)
            output z
            n /= z

        else
            z++

    if n > 1
        output n

我将留给您使用适当的整数数据类型转换为C++.

编辑:修正比较(谢谢,Harold)并为Bob John添加了讨论:

理解这一点的最简单方法是通过一个例子.考虑n = 13195的因子分解.最初z = 2,但是将13195除以2会得到1的余数,所以else子句设置z = 3并且我们循环.现在n不能被3或4整除,但是当z = 5时,将13195除以5时的余数为零,因此输出5并将13195除以5使得n = 2639并且z = 5不变.现在新的n = 2639不能被5或6整除,但是可以被7整除,所以输出7并设置n = 2639/7 = 377.现在我们继续z = 7,剩下的就像是除法一样通过8,9和10,11和12,但377/13 = 29没有余数,所以输出13并设置n = 29.此时z = 13,z*z = 169,这是大于29,所以29是素数并且是13195的最终因子,因此输出29.完全因子分解为5*7*13*29 = 13195.

有更好的算法可以使用试验除法对整数进行因子分解,甚至更强大的算法可以使用除了试验除法之外的技术对整数进行因式分解,但上面显示的算法可以帮助您入门,并且足以用于Project Euler#3.当你准备好了更多时,请看这里.