Question

c语言，用分解质因数的方法求两个数的最大公约数

void fenjie(int n)
{
int i;
printf("%d=",n);

while(n%2==0){
printf("%d*",2);
n/=2;
}
for(i=3;i<=sqrt(n);i+=2)
{
if(n%i==0)
{
n/=i;
printf("%d*",i);
i-=2;
}

}
printf("%d\n",n);

}
int main(){
int a;
scanf("%d",&a);
fenjie(a);

return 0;
}
分解质因数已经写好，然后求大神补全代码!!!

Answer 1

主要通过循环控制语句求去两个数的最大公约数。

具体的实现方法可以参考如下函数：

// 最大公约数函数
int GreatestCommonDivisor(int m, int n)
{
    int temp;
    if(m<n)  // 取m，n中较大的一个数，m中存放较大的数，n中存放较小的数
    {
    // 不通过引入中间变量，通过异或运算来交换两个数的值
        m = m^n;
        n = n^m;
        m = m^n;
    }
    temp = m % n;  // 取出m除以n的余数
    // 反复分解质因数进行求最大公约数
    while(temp)
    {
        m = n;  // 将n值赋值给m
        n = temp;  // 将余值赋值给n
        temp = m % n; // 求余
    }
    return n;  // 返回最大公约数
}

Answer 2

主要通过循环控制语句求去两个数的最大公约数。
具体的实现方法可以参考如下函数：
// 最大公约数函数
int GreatestCommonDivisor(int m, int n)
{
int temp;
if(m
评论
0
0
0
加载更多

Answer 3

求最大公约数为什么要分解质因数？分别得到两个数的质因数序列，怎么求公约数呢