如何用C语言实现一个递归和非递归的方法，分别找出大于1的自然数n的所有质数因子？

在C语言中，我们可以使用递归和循环的方式分别实现查找大于1的自然数n的所有质数因子。这里给出两个示例：

**非递归方法 - 遍历分解法：**

#include <stdio.h>

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

// 找出所有质数因子
void prime_factors(int n, int current_factor, int* factors, int count) {
    if (current_factor > n || !is_prime(current_factor)) {
        // 如果当前不是质数，结束递归
        return;
    }

    // 检查当前因素是否可以整除n
    while (n % current_factor == 0) {
        factors[count++] = current_factor; // 记录因子
        n /= current_factor;
    }
    // 继续寻找下一个质数因子
    prime_factors(n, current_factor + 1, factors, count);
}

// 主函数测试
int main() {
    int n, i;
    printf("Enter a number: ");
    scanf("%d", &n);

    int factors[n], factor_count = 0;
    prime_factors(n, 2, factors, factor_count);

    printf("Prime factors of %d are: ", n);
    for (i = 0; i < factor_count; i++)
        printf("%d ", factors[i]);
    printf("\n");

    return 0;
}

**递归方法 - 回溯法：**

#include <stdio.h>
#include <stdbool.h> // 添加bool类型支持

// 递归版的质数判断
bool recursive_is_prime(int num, int i) {
    if (num <= 1) return false;
    if (i * i > num) return true;
    if (num % i == 0) return false;
    return recursive_is_prime(num, i + 1);
}

// 递归找质数因子
void recursive_prime_factors(int n, int current_factor, int* factors, int* count) {
    if (current_factor > n) return;

    if (recursive_is_prime(current_factor, 2)) {
        *count += 1; // 增加计数
        factors[*count] = current_factor;
        
        // 分解因子
        while (n % current_factor == 0) {
            n /= current_factor;
        }
        recursive_prime_factors(n, current_factor, factors, count);
    } else {
        recursive_prime_factors(n, current_factor + 1, factors, count);
    }
}

// 主函数测试
int main() {
    int n, i;
    printf("Enter a number: ");
    scanf("%d", &n);

    int factors[100];
    int factor_count = 0;
    recursive_prime_factors(n, 2, factors, &factor_count);

    printf("Prime factors of %d are: ", n);
    for (i = 0; i < factor_count; i++)
        printf("%d ", factors[i]);
    printf("\n");

    return 0;
}