寻找主要因素 [英] Finding prime factors

问题描述

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

我试图找到数字600851475143的质数因子， a Href =https://projecteuler.net/problem=3 =nofollow>问题3 在项目Euler（它要求最高的素因子，但我想找到所有的）。但是，当我尝试运行这个程序，我没有得到任何结果。它与我的程序花费多长时间，甚至与数字本身有关？

I'm trying to find the prime factors of the number 600851475143 specified by Problem 3 on Project Euler (it asks for the highest prime factor, but I want to find all of them). However, when I try to run this program I don't get any results. Does it have to do with how long my program is taking for such a large number, or even with the number itself?

此外，什么是一些更有效的方法来解决这个问题，你有什么提示，如何解决这些更优雅的解决方案，因为我正在解决一个问题？

Also, what are some more efficient methods to solve this problem, and do you have any tips as to how can I steer towards these more elegant solutions as I'm working a problem out?

一如往常，谢谢！

推荐答案

您的算法有误;您不需要 i 。这里是通过试验划分的整数分解的伪代码：

Your algorithm is wrong; you don't need i. Here's pseudocode for integer factorization by trial division:

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 ++，整数数据类型。

I'll leave it to you to translate to C++ with the appropriate integer datatypes.

编辑：修正比较（感谢Harold），并添加了对Bob John的讨论：

Fixed comparison (thanks, Harold) and added discussion for 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。

The easiest way to understand this is by an example. Consider the factorization of n = 13195. Initially z = 2, but dividing 13195 by 2 leaves a remainder of 1, so the else clause sets z = 3 and we loop. Now n is not divisible by 3, or by 4, but when z = 5 the remainder when dividing 13195 by 5 is zero, so output 5 and divide 13195 by 5 so n = 2639 and z = 5 is unchanged. Now the new n = 2639 is not divisible by 5 or 6, but is divisible by 7, so output 7 and set n = 2639 / 7 = 377. Now we continue with z = 7, and that leaves a remainder, as does division by 8, and 9, and 10, and 11, and 12, but 377 / 13 = 29 with no remainder, so output 13 and set n = 29. At this point z = 13, and z * z = 169, which is larger than 29, so 29 is prime and is the final factor of 13195, so output 29. The complete factorization is 5 * 7 * 13 * 29 = 13195.

是使用试分法对整数进行因式分解的更好的算法，甚至更强大的算法用于使用除试验除法之外的技术，但是上面显示的算法将使您开始，并且足够用于项目Euler＃3。当您准备好了解更多时，请在这里。

There are better algorithms for factoring integers using trial division, and even more powerful algorithms for factoring integers that use techniques other than trial division, but the algorithm shown above will get you started, and is sufficient for Project Euler #3. When you're ready for more, look here.

这篇关于寻找主要因素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！