失败的质因数分解程序 (c++)

Question

我正在尝试解决 this 编程问题。这是问题。

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

现在我编写了一个 c++ 程序，它试图通过暴力检查它，然而，在执行它时卡在 5。这是程序

#include <iostream>
#include <math.h>
using namespace std;
const long long no = 600851475143;

long long isprime(long long p)
{
    long long reply = -1;
    long long i = 2;
    while (i < pow(p, 0.5)) {
        if (i % p == 0)
            reply = i;
    }
    if (reply == -1){
    return 0;
    cout<<" yup its prime "<<endl;  
    }

    else
        return reply;
}

long long factor(long long x)
{
     for (long long i = 2; i < no; i++) {
    cout<<"Trying "<<i<<endl;
        if ((isprime(i) == 0)&& (no % i == 0)) {
            return i;
        cout<<"found "<<i<<endl;
            break;
        }
    }
}

int main()
{
    long long ans = no;
    while (ans != 1) {
        cout << factor(ans) << endl;
        ans = ans / factor(ans);
    }
}

这是输出

~/Desktop/proj$ ./a.out 

Trying 2
Trying 3
Trying 4
Trying 5

我真的不明白为什么卡在5号，谁能帮帮我？

编辑：谢谢 b13rg，我意识到我的错误。我现在有一个更好的算法，我把它贴下来供需要的人使用。

#include<iostream>
#include<math.h>
using namespace std;

long long fun (long long x)
{
    for(long long i=2; i<sqrt(x);i++){
    while (x%i==0){
        cout<<i<<endl;
        x=x/i;
        }   
    }
}

int main(){

fun(600851475143);


return 0;}

Answer 1

你似乎从来没有在函数isprime 的while 循环中改变i 或p 的值。它失败了，因为 sqrt(5) 大于 2，并且 while 循环中的任何内容都没有改变。

对于您要解决的问题：

您可以首先通过仅尝试奇数来优化检查循环，因此首先执行 2，然后 3，然后 5 等。为了使其更快，您可以在前几个素数中进行硬编码，但这可能超出这个项目的范围。

要找到最大的质因数，您需要先找到最小的质因数。比如上面这个数，最小的是5，接下来就是13195除以5得到2369，然后重新开始寻找这个数的最小质因数，一直往下直到除以质数。

Number|Smallest prime
------|--------------
13169 | 5
2369  | 7
377   |13
29    |Largest prime factor of 13169

失败的质因数分解程序 (c++)

Failing prime factorisning program (c++)

c++

loops

debugging

prime-factoring