分解质因数 动态规划 C语言
时间: 2024-02-16 09:58:59 浏览: 53
分解质因数是指将一个正整数分解成若干个质数的乘积的过程。动态规划是一种解决问题的算法思想,通过将问题分解为子问题,并保存子问题的解来避免重复计算,从而提高算法的效率。下面是使用动态规划解决分解质因数的C语言代码示例:
```c
#include <stdio.h>
void factorize(int n) {
int dp[n+1]; // 用于保存每个数的最小质因数
dp[1] = 1; // 1不是质数,最小质因数为1
for (int i = 2; i <= n; i++) {
if (dp[i] == 0) { // 当前数i是质数
for (int j = i; j <= n; j += i) {
if (dp[j] == 0) { // 如果当前数j没有最小质因数
dp[j] = i; // 设置j的最小质因数为i
}
}
}
}
printf("%d = ", n);
while (n > 1) {
printf("%d", dp[n]);
n /= dp[n];
if (n > 1) {
printf(" * ");
}
}
printf("\n");
}
int main() {
int num;
printf("请输入一个正整数:");
scanf("%d", &num);
factorize(num);
return 0;
}
```
运行以上代码,输入一个正整数,即可输出该数的质因数分解结果。