用c语言求两个自然数m和n的最大公约数。有以下要求 用分解质因数法 1、将m分解质因数; 2、将n分解质因数; 3、提取m和n中的公共质因数; 4、将n和n中的公共质因数相乘,乘积作为结果输出。
时间: 2024-10-10 07:13:13 浏览: 6
要用C语言按照分解质因数法求两个自然数`m`和`n`的最大公约数,可以按以下步骤操作:
1. **定义函数**:创建一个名为`gcd_by_prime_factors`的函数,接收两个整数参数`m`和`n`。
```c
#include <stdio.h>
#include <stdbool.h>
// 函数声明,用于分解质因数
bool prime_factorize(int num, int* factors, int count);
```
2. **分解质因数**:`prime_factorize`函数会分解一个数`num`成质因数,并将结果存储在一个数组`factors`中,返回一个布尔值表示是否成功找到所有质因数。
```c
bool prime_factorize(int num, int* factors, int count){
if(num <= 1)
return false;
for(int i = 2; i * i <= num; ++i){
if(num % i == 0){
factors[count++] = i;
num /= i;
continue;
}
while(num % i == 0){
factors[count++] = i;
num /= i;
}
}
// 如果num是质数,则将其添加到factors数组
if(num > 1)
factors[count++] = num;
return true;
}
```
3. **提取公共质因数**:在主函数`main`中,先分别调用`prime_factorize`函数分解`m`和`n`的质因数,然后遍历其中一个的质因数数组,查找另一个数组中存在的公共质因数。
```c
int main() {
int m, n;
printf("请输入两个自然数m和n:");
scanf("%d%d", &m, &n);
int m_factors[100], m_count = 0;
bool m_result = prime_factorize(m, m_factors, m_count);
int n_factors[100], n_count = 0;
bool n_result = prime_factorize(n, n_factors, n_count);
// 检查分解结果并找出公共质因数
int common_count = 0;
for(int i = 0; i < m_count && i < n_count; ++i){
if(m_factors[i] == n_factors[i]){
common_count++;
// 更新最大公约数为公共质因数的乘积
m_factors[common_count-1] *= n_factors[i];
}
}
printf("最大公约数是:%d\n", m_factors[common_count]);
return 0;
}
```
4. **检查输入合法性**:这里假设用户输入的是合法的自然数。如果需要处理非自然数的情况,可以在读取用户输入后检查,并相应地调整程序。