为什么它显示主要因素的错误输出？

Question

我制作这个程序是为了找到一个数的质因数，但是当我运行这个代码时它给出了错误的输出。我已经调试了这段代码，逻辑也是正确的。我发现，当 "x == 1" 程序出现异常时。我找不到答案。

#include<stdio.h>
void prime(int );
main()
{
    int num;

    printf("Enter a number to find its prime factors: ");
    scanf("%d", &num);

    printf("\nPrime factors of %d are: \n", num);

    prime(num);
}

void prime(int x)
{
    int i = 2;

    while(x != 1)
    {
        if(x % i == 0)
        {
            printf("%d, ", i);

            x = x / i;
            prime(x);
        }

        else
        {
            i++;
        }

    }
}

Answer 1

一旦找到第一个除数，就应该退出循环。否则，您的外部方法调用将继续搜索您的 x 的除数，即使它不再需要：

void prime(int x) {
    if (x == 0) {
        printf("All prime numbers are prime factors of 0");
        return;
    }

    if (x == INT_MIN) {
        printf("Please provide a number larger than %i", INT_MIN);
        return;
    }

    x = abs(x);
    int i = 2;
    while(x != 1) {
        if(x % i == 0) {
            printf("%d, ", i);

            x = x / i;
            prime(x);
            break; // break here
        }
        i++;
    }
}

更新

然而，这里实际上不需要递归 - 相反，您可以使用如下简单的迭代算法：

void prime(int x) {
    if (x == 0) {
        printf("All prime numbers are prime factors of 0");
        return;
    }

    if (x == INT_MIN) {
        printf("Please provide a number larger than %i", INT_MIN);
        return;
    }

    x = abs(x);
    int i = 2;
    while (x != 1) {
        if (x % i == 0) {
            printf("%d, ", i);
            x = x / i;
        }
        i++;
    }
}

Answer 2

您的意思似乎是下面的演示程序中所示的递归函数：

#include <stdio.h>

void prime( unsigned int x )
{
    if ( !( x < 2 ) )
    {
        unsigned int i = 2;

        while ( x % i ) ++i;

        printf( "%u, ", i );

        prime( x / i );
    }       
}

int main(void) 
{
    unsigned int num;

    printf( "Enter a number to find its prime factors: " );
    scanf( "%u", &num );

    printf( "\nPrime factors of %u are: \n", num );

    prime( num );   

    putchar( '\n' );

    return 0;
}

程序输出可能如下所示：

Enter a number to find its prime factors: 10
Prime factors of 10 are: 
2, 5,

也就是函数的递归调用应该放在while循环之外

Answer 3

既然要求上面代码的"DEBUG"，我打算用同样的逻辑来回答问题。

循环计数变量"i"需要是静态变量
缺少递归的中断条件。

固定代码：

#include<stdio.h>
void prime(int );
main()
{
    int num;

    printf("Enter a number to find its prime factors: ");
    scanf("%d", &num);

    printf("\nPrime factors of %d are: \n", num);

    prime(num);
}

void prime(int x)
{
    static int i = 2;

    while(x != 1 && i <= x)
    {
        if(x % i == 0)
        {
            printf("%d, ", i);

            x = x / i;
            i++;
            prime(x);
            break;
        }

        else
        {
            i++;
        }

    }
}

Answer 4

选择递归方法时，关键步骤之一就是确定停止条件。

已发布代码中的（或至少一个）问题是递归调用是在内部 while 循环中进行的，因此可以找到质因数并打印多次 .

我也会避免每次都从 2 重新开始因子搜索，但在那种情况下，您应该向递归函数添加一个参数。下面，我把质因数分解的逻辑拆分成了两个函数，其中只有一个是递归的。

void prime_impl(int n, int factor, const char* delim)
{
    if (n < 2)
        return;

    while (factor <= n  &&  n % factor)
        ++factor;

    printf("%s%d", delim, factor);

    prime_impl(n / factor, factor, " * ");
}

void prime_factorization(int n)
{
    printf("%4d", n);
    if ( n < 0 )
        prime_impl(-n, 2, " = ");
    else
        prime_impl(n, 2, " = ");
    putchar('\n');
}

可测试here。

为什么它显示主要因素的错误输出？

why it's showig wrong output for prime factors?

c

recursion

while-loop

prime-factoring

factors