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

Question

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

关于c++ - 我无法在代码中找到最大的素数错误？ ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62024824/

上一篇：c++ - 变量 'sortArray'周围的堆栈已损坏

下一篇：c++ - 为什么我将nan作为以下代码的输出？

相关文章：

c++ - "omp single"和 "omp task"如何提供并行性？

javascript - 在半圆内绘制点

python - python 中的数值方法 - 无法发现问题？

java - 如何使用 Apache Commons Math 中的 PolynomialSplineFunction

c++ - 使用 C++ 将哈希表复制到另一个哈希表

c++ - C++的专业品质图表库

c++ - 通过 clang-format 格式化 lambda 背后的逻辑是什么？

c++ - 如何在现代 opengl 中处理正交投影中的照明？

ios - Swift，如何使用数组中存储的数字进行数学运算

algorithm - 什么算法可以让一个数字最接近一个可以均匀(在一定范围内)分成两个其他常数的常数？

Answer 1

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

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