分解质因数求最大公约数

Question

代码没问题就是结果一直为一放不了代码没办法11111112111111很简单的问题但是卡住我了有没有人帮忙看看的

Answer 1

应该是因为分解质因数和计算m和n的公共质因数那里需要改进下，修改如下：

参考链接：

https://www.bejson.com/other/common_divisor/

https://blog.csdn.net/weixin_39737636/article/details/116988808

https://blog.csdn.net/weixin_29234423/article/details/116982469

#include<iostream>
using namespace  std;
int fenjie() {

    int m,n;
    cout<<"请输入m：";
    cin>>m;

    cout<<"请输入n：";
    cin>>n;

    int i,j;
    int c=0;
    int d=0;
    int result=1;
    int a[100],b[100];

    i=2;
    while(m!=1&&i<m) { // 计算m的质因数 

        while(m%i==0) {
            a[c]=i;
            m=m/i;
        //    printf("a[%d]=%d\n",c,a[c]);
        //    printf("i=%d,m=%d\n",i,m);
            if(m!=1) {
                c++;
            } else {
                break;
            }
        }
        i++;

    }

    i=2;
    while(n!=1&&i<n) {  // 计算n的质因数 

        while(n%i==0) {
            b[d]=i;
            n=n/i;
        //    printf("b[%d]=%d\n",d,b[d]);
        //    printf("i=%d,n=%d\n",i,n);
            if(n!=1) {
                d++;
            } else {
                break;
            }
        }
        i++;

    }


    i=0;
 // 求m和n的公共质因数 ，从m的第一个质因数逐个与n的每个质因数比较，如果相同，则累乘到结果中    
    while(i<=c) { 
        
        j=0;
        while(j<=d&&i<=c) { // 重复遍历n的每个质因数  
            
            if(a[i]==b[j]&&b[j]!=-1) {  //如果质因数相同，则累乘到结果中，同时将n的质因数数组此位置置-1，下次不再比较 
                result*=a[i];
            //    printf("a[%d]=%d,b[%d]=%d,result=%d\n",i,a[i],j,b[j],result);
                b[j]=-1;
                i++;  // 判断m的下一个质因数            
            }
            j++;  // 判断n的下一个质因数 
        }
        
        i++;  // 上面的循环结束，说明需要判断m的下一个质因数了 
    }

    return result;
}
int main() {

    cout<<"结果为 ："<<fenjie();
    return 0;

}