c++ - 我无法在代码中找到最大的素数错误？

Closed. This question needs debugging details。它当前不接受答案。












想改善这个问题吗？更新问题，以便将其作为on-topic用于堆栈溢出。

在6个月前关闭。



Improve this question




我已经编写了一个代码，以查找迄今为止最大的素因数，该最大的素因数已经针对我测试过的每种情况起作用，但是当我输入600851475143时失败了。它一直给我5102831，这是不正确的。我不确定为什么会发生这种情况，即使我已经检查了它，也将不胜感激。

#include <iostream>

long int get_largest_prime_factor(long int);

int main()
{
    std::cout << get_largest_prime_factor(600851475143);
    return 0;
}

long int get_largest_prime_factor(long int prime_Number)
{
    for(long int r = prime_Number - 1; r != 1; r--)
    {
        if(prime_Number % r == 0)
        {
            long int a = get_largest_prime_factor(r);
            long int b = get_largest_prime_factor(prime_Number / r);
            if(a == b)
                return a;
            return a > b? a : b;
        }
    }
    return prime_Number;
}

最佳答案

使用此简单算法即可获取正确的素数:

long long int getMaxPrimeFactor(long long int n) {
    int i, max = -1;

    while (n % 2 == 0) {
        max = 2;
        n /= 2;
    }

    for (i = 3; i <= sqrt(n); i = i + 2)
        while (n % i == 0) {
            max = i;
            n /= i;
        }

    max = (n > 2) ? n : max;
    return max;
}

这应该输出:

6857