探索求解最大公约数的四种高效算法

一、最大公约数与最小公倍数

最大公约数&＃xff0c;属于数论所探究的内容。

最大公约数可以通过下面的三种方法求出来。

最小公倍数呢&＃xff0c;它与最大公约数的乘机为所求数之积。

比如求 x,y的最大公约数和最小公倍数

记住这个公式&＃xff1a; xy&＃61;最小公倍数最大公约数

二、求最大公约数的三种方法

①辗转相除法
算法流程图

代码块&＃xff1a;

int measure(int x, int y)
{ int z &＃61; y;while(x%y!&＃61;0){z &＃61; x%y;x &＃61; y;y &＃61; z; }return z;
}


运行结果:

②辗转相减法

代码块&＃xff1a;

int measure(int a,int b)
{ while(a !&＃61; b){if(a>b){a &＃61; a - b;}else {b &＃61; b - a;}}return a;
}


运行结果&＃xff1a;

③穷举法
流程图&＃xff1a;

代码块&＃xff1a;

int measure(int x,int y)
{int temp &＃61; 0;for(temp &＃61; x ; ; temp-- ){if(x%temp &＃61;&＃61; 0 && y%temp&＃61;&＃61;0) break; }return temp;
}


④递归法

int gcd (int x, int y){if (y&＃61;&＃61;0)return x;else return gcd (y,x%y); }/* 辗转相除法基于如下原理&＃xff1a;两个整数的最大公约数等于其中较小的数和两数的相除的余数的最大公约数那y和x%y如果余数为0&＃xff0c;那y不就是最大公约数补充&＃xff1a;两个数的最小公倍数等于 x*y/gcb(x,y);
*/