c - 在c中使用递归找到最大素因数

Question

已经编写了我认为是一个很好的算法的代码，用于使用递归查找大量数字的最大素因数。不过，当分配给变量huge_number 的任何大于4 的数字时，我的程序都会崩溃。我不擅长递归，并且赋值不允许任何类型的循环。

#include <stdio.h>

long long prime_factor(int n, long long huge_number);

int main (void)
{
    int n = 2;
    long long huge_number =  60085147514;
    long long largest_prime = 0;

    largest_prime = prime_factor(n, huge_number);
    printf("%ld\n", largest_prime);

    return 0;
}

long long prime_factor (int n, long long huge_number)
{
    if (huge_number / n == 1)
        return huge_number;
    else if (huge_number % n == 0)
        return prime_factor (n, huge_number / n);        
    else
        return prime_factor (n++, huge_number);
}

任何有关它崩溃的原因以及我如何改进它的信息将不胜感激。

Answer 1

即使解决了使用后递增的问题以使递归永远持续下去，这也不太适合递归解决方案 - 请参阅 here为什么，但这归结为减少搜索空间的速度。

虽然 huge_number 的除法很快就能减少它，但绝大多数递归调用都是通过简单地增加 n 来完成的。这意味着您将使用大量堆栈空间。

您的情况会更好:

• 使用不会耗尽堆栈的迭代解决方案(如果您只是想解决问题)^(a);或
• 如果您只是想学习递归，请找到更适合递归的问题。

---

^(a) 这种野兽的一个示例(以递归解决方案为模型)是:

#include <stdio.h>

long long prime_factor_i (int n, long long huge_number) {
    while (n < huge_number) {
        if (huge_number % n == 0) {
            huge_number /= n;
            continue;
        }
        n++;
    }
    return huge_number;
}

int main (void) {
    int n = 2;
    long long huge_number =  60085147514LL;
    long long largest_prime = 0;

    largest_prime = prime_factor_i (n, huge_number);
    printf ("%lld\n", largest_prime);

    return 0;
}

---

从该迭代解决方案的输出中可以看出，最大的因子是10976461。这意味着递归解决方案中的最后一批递归将需要一千万个堆栈帧的堆栈深度，这不是大多数环境能够轻松应对的。

如果您确实必须使用递归解决方案，则可以利用您没有有检查的事实，将堆栈空间减少到其平方根一直到数字，但只到其平方根。

此外，除了2之外，其他所有素数都是奇数，因此您可以通过仅检查两个加上奇数来进一步将搜索空间减半。

考虑到这两件事的递归解决方案是:

long long prime_factor_r (int n, long long huge_number) {
    // Debug code for level checking.

    // static int i = 0;
    // printf ("recursion level = %d\n", ++i);

    // Only check up to square root.

    if (n * n >= huge_number)
        return huge_number;

    // If it's a factor, reduce the number and try again.

    if (huge_number % n == 0)
        return prime_factor_r (n, huge_number / n);

    // Select next "candidate" prime to check against, 2 -> 3,
    //   2n+1 -> 2n+3 for all n >= 1.

    if (n == 2)
        return prime_factor_r (3, huge_number);

    return prime_factor_r (n + 2, huge_number);
}

您可以看到我还删除了(在我看来，这很尴尬)构造:

if something then
    return something
else
    return something else

我更喜欢来自以下缩进较少的代码:

if something then
    return something
return something else

但这只是个人喜好。无论如何，这会让你的递归级别降低到 1662(取消注释调试代码以进行验证)而不是 1000 万，这是一个相当大的减少，但仍然不完美。在我的环境中运行正常。