首页用C语言写递归函数求出给定自然数 n（n>1）的所有（质数）因子。例如：72 = 2

用C语言写递归函数求出给定自然数 n（n>1）的所有（质数）因子。例如：72 = 2

时间: 2024-12-11 14:23:06 AIGC 浏览: 59

在C语言中，我们可以编写一个递归函数来寻找一个给定自然数n的所有质因数。这里是一个简单的示例，它使用了欧几里得算法来确定最大公约数，并检查是否为质数： ```c #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 factor, int* result) { if (n == 1) { // 如果当前因子仍存在，则它是质因数 if (*result != factor) result[(*result)++] = factor; return; } // 使用当前因子去除n，如果能整除说明找到了质因子 while (n % factor == 0) { n /= factor; if (!is_prime(factor)) break; // 如果不是质数，跳出循环 } // 如果因子仍是原样，则递归查找下一个质因数 if (factor > 1) { prime_factors(n, factor, result); } } int main() { int n = 72; int factors[50]; int count = 0; prime_factors(n, 2, factors); printf("The prime factors of %d are: ", n); for (int i = 0; i < count; i++) { printf("%d ", factors[i]); } printf("\n"); return 0; } ``` 在这个例子中，`prime_factors` 函数会首先尝试将 `n` 除以 `factor`，如果 `factor` 能整除 `n` 并且是质数，那么它就是 `n` 的一个质因子。然后递归地调用自身，直到 `n` 变为 1。注意，这个程序没有处理结果数组的大小，因此对于较大的输入值可能需要更大的数组。另外，实际应用中可能还需要更高效的算法来避免无限递归和过大的内存消耗。

阅读全文