下面列出了三种方式求两数的最大公约数,另外还有一个公式:ab=最大公约数最小公倍数

1.辗转相除法

    int max_gys(int a, int b)
    {    
    int c = b;//保证两数相同是可直接输出结果
    while(a%b!=0)
    {
        c = a%b;
        a = b;
        b = c;    
    }
    return c;
    }

2.辗转相减法

    int max_gys(int a,int b)
     {        
    while(a != b)//当减到两数相等时任意一个数就是原两者的最大公约数
    {
        if(a>b)
        {
            a = a - b;
        }
        else 
        {
            b = b - a;
        }
    }
    return b;
     }

3.枚举法(穷举法)

    int max_gys(int a,int b)
     {        
       int item=a;//这里是两个数任意一个,公约数大小不会超过两个数任意一个的
       while(1)
        {   
            if(a%item==0&&b%item==0)
             break;
             item--;
        }
        return item;
    }
Last modification:April 3rd, 2020 at 06:31 pm
如果觉得我的文章对你有用,请随意赞赏