求最大公约数的4种方法

您所在的位置：网站首页 › 递归求最大公约数python › 求最大公约数的4种方法

求最大公约数的4种方法

2024-05-26 07:41| 来源: 网络整理| 查看: 265

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

最大公约数，属于数论所探究的内容。

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

最小公倍数呢，它与最大公约数的乘机为所求数之积。

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

记住这个公式： xy=最小公倍数最大公约数

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

①辗转相除法算法流程图在这里插入图片描述代码块：

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

运行结果: 在这里插入图片描述 ②辗转相减法代码块：

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

运行结果：在这里插入图片描述 ③穷举法流程图：代码块：

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

④递归法

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

在这里插入图片描述

【本文地址】

求最大公约数的4种方法

求最大公约数的4种方法

今日新闻

推荐新闻