用递归实现分解质因数。形如：12=2*2*3。用c语言递归写出程序

以下是用C语言递归实现分解质因数的示例[^1]：

#include <stdio.h>
int i = 2; // 定义全局变量

void func(int num) {
    // 递归结束条件
    if (num / i <= 1 && num % i == 0) {
        printf("%d", i);
        return;
    }
    
    // 如果i是因子，输出并递归处理剩余部分
    if (num % i == 0) {
        printf("*%d", i);
        func(num / i);
    }
    
    // 若i不是因子，则递增i并继续尝试
    else {
        i++;
        func(num);
    }
}

int main() {
    int num;
    scanf("%d", &num);
    func(num); // 调用分解函数
    return 0;
}

这段代码通过递归方式分解给定的正整数`num`成质因数，比如输入12时会输出`12=2*2*3`。

相关问题--:
1. 递归方法是如何确定每个质因子的？
2. C语言中为什么要在`main()`函数外部定义变量`i`？
3. 如何优化这段代码以减少重复计算？

相关问题

用最基础的c语言打印分别编写递归和非递归的函数，求出给定自然数n （n>1）的所有（质数） 因子。例如：72 = 2*2*2*3*3

在C语言中，我们可以用递归和循环两种方法来找出给定自然数n的所有质因数。这里分别给出两种方法的基本示例：

**非递归方法（循环法）：**

#include <stdio.h>

void find_factors(int n) {
    int i;
    for (i = 2; i * i <= n; i++) { // 只检查到根号n，因为大于这个数的因子必定有一个小于等于它的平方根
        while (n % i == 0) { // 当i是n的因子时，去除并记录因子
            printf("%d ", i);
            n /= i;
        }
    }

    if (n > 1) { // 如果n还有剩余，说明最后一个因子就是n本身
        printf("%d", n);
    }
}

int main() {
    int n = 72;
    find_factors(n);
    return 0;
}

**递归方法：**

#include <stdio.h>
int is_prime(int num, int divisor = 2) { // 判断是否为质数的基础情况
    if (num <= 1)
        return 0;
    else if (num == 2)
        return 1;
    else if (num % divisor == 0)
        return 0;
    else
        return is_prime(num, divisor + 1); // 递归处理除1和自身外的情况
}

void find_factors_recursive(int n) {
    if (is_prime(n)) { // 如果n是质数，直接输出
        printf("%d ", n);
    } else {
        int factor = 2;
        while (!is_prime(n, factor)) { // 非递归部分找到下一个因子
            factor++;
        }
        printf("%d ", factor); // 输出当前因子

        n /= factor; // 更新n值，移除已知的因子
        find_factors_recursive(n); // 递归处理剩下的因子
    }
}

int main() {
    int n = 72;
    find_factors_recursive(n);
    return 0;
}

以上代码会分别输出数字72的所有质因数。

用c语言或C++且用递归算法分解质因数。对给定区间[m,n]的正整数分解质因数,口每一整数表示为质因数从 小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。 例如,2012=2*2*503,2011=(素数!)。

以下是用C语言实现的递归算法分解质因数的代码：

#include <stdio.h>

// 判断一个数是否为质数
int isPrime(int n) {
    if (n < 2) {
        return 0;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

// 分解质因数
void decompose(int n) {
    if (isPrime(n)) { // 如果n本身是质数，直接输出
        printf("%d", n);
        return;
    }
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) { // 找到n的一个因子i
            printf("%d*", i); // 输出i和一个乘号
            decompose(n / i); // 递归分解n/i
            break;
        }
    }
}

int main() {
    int m, n;
    printf("请输入区间[m,n]的m和n：");
    scanf("%d%d", &m, &n);
    printf("区间[%d,%d]内的正整数分解质因数结果如下：\n", m, n);
    for (int i = m; i <= n; i++) {
        printf("%d=", i);
        decompose(i);
        printf("\n");
    }
    return 0;
}

递归算法分解质因数的思路是：先判断待分解的数n是否为质数，如果是，则直接输出n；否则，找到n的一个因子i，输出i和一个乘号，然后递归分解n/i。这样，就可以将n分解为若干个质数的乘积。在主函数中，我们输入区间[m,n]的m和n，然后对区间内的每个正整数i都进行分解质因数，输出结果。