在c中使用递归找到最大的素数 [英] finding greatest prime factor using recursion in c

问题描述

已经编写了代码，我认为这是一个很好的算法，可以使用递归找到大数的最大质因数.但是，我的程序在分配给变量 huge_number 的任何大于 4 的数字时崩溃.我不擅长递归，并且分配不允许任何类型的循环.

have wrote the code for what i see to be a good algorithm for finding the greatest prime factor for a large number using recursion. My program crashes with any number greater than 4 assigned to the variable huge_number though. I am not good with recursion and the assignment does not allow any sort of loop.

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

关于它为什么崩溃以及我如何改进它的任何信息将不胜感激.

any info as to why it is crashing and how i could improve it would be greatly appreciated.

推荐答案

即使修复了使用后增量的问题，使递归永远持续下去，这也不适合递归解决方案 - 参见 此处 了解原因，但归结为减少搜索空间的速度有多快.

Even fixing the problem of using post-increment so that the recursion continues forever, this is not a good fit for a recursive solution - see here for why, but it boils down to how fast you can reduce the search space.

虽然您对 huge_number 的划分会很快减少它，但绝大多数递归调用都是通过简单地增加 n 来完成的.这意味着您将使用很多的堆栈空间.

While your division of huge_number whittles it down pretty fast, the vast majority of recursive calls are done by simply incrementing n. That means you're going to use a lot of stack space.

你最好:

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

^(a) 以您的递归解决方案为模型的此类野兽的示例是:

^(a) An example of such a beast, modeled on your recursive solution, is:

#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.这意味着您的递归解决方案中的最后一批递归将需要一千万个百万 堆栈帧的堆栈深度，而大多数环境都不会轻易应对.

---

As can be seen from the output of that iterative solution, the largest factor is 10976461. That means the final batch of recursions in your recursive solution would require a stack depth of ten million stack frames, not something most environments will contend with easily.

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

If you really must use a recursive solution, you can reduce the stack space to the square root of that by using the fact that you don't have to check all the way up to the number, but only up to its square root.

另外，除了2，其他的素数都是奇数，所以你可以通过只检查两个加上奇数的方式进一步减半搜索空间.

In addition, other than 2, every other prime number is odd, so you can further halve the search space by only checking two plus the odd numbers.

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

A recursive solution taking those two things into consideration would be:

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

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

You can see I've also removed the (awkward, in my opinion) construct:

if something then
    return something
else
    return something else

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

I much prefer the less massively indented code that comes from:

if something then
    return something
return something else

但这只是个人喜好.在任何情况下，这都会使您的递归级别降低到 1662(取消注释要验证的调试代码)而不是 1000 万，这是相当可观的减少，但仍然不完美.在我的环境中运行正常.

But that's just personal preference. In any case, that gets your recursion level down to 1662 (uncomment the debug code to verify) rather than ten million, a rather sizable reduction but still not perfect. That runs okay in my environment.

这篇关于在c中使用递归找到最大的素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！