c++ - 寻找主要因素

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

我试图找到由 Problem 3 指定的数字 600851475143 的质因数在 Project Euler 上(它要求最高素数，但我想找到所有素数)。但是，当我尝试运行这个程序时，我没有得到任何结果。它是否与我的程序处理如此大的数字所花费的时间有关，甚至与数字本身有关？

另外，有什么更有效的方法可以解决这个问题？对于我在解决问题时如何转向这些更优雅的解决方案，您有什么建议吗？

一如既往，谢谢!

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, and 9, and 10, and 11, and 12, but 377/13 = 29 没有余数，所以输出13，设n = 29。此时z = 13, and z * z = 169, 即大于 29，所以 29 是素数，是 13195 的最终因子，所以输出 29。完全分解为 5 * 7 * 13 * 29 = 13195。

使用试除法分解整数有更好的算法，使用试除法以外的技术分解整数的算法甚至更强大，但上面显示的算法将帮助您入门，并且足以满足欧拉计划 #3 的要求。当您准备好获取更多信息时，请查看 here .