【算法】欧几里德算法(辗转相除法)求最大公约数

浅浅的花香味﹌ 2022-04-10 07:16 156阅读 0赞

> 定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

**gcd(a,b) = gcd(b,a mod b)** (不妨设a>b 且r=a mod b ,r不为0)  
则有：**gcd(a, b) = gcd(b, a%b) = gcd(a%b, (b%(a%b))) = … … = gcd(c, 0) = c**

#### 证明： ####

> 我们首先约定：m = gcd(a,b) , n = gcd(b, q) , a = b\*p +q。  
> （这里的gcd含义跟上面一样，q的含义跟后面式子同）
> 
> 1.  =>m 是a,b的最大公约数，那么m整除a,b  
>     =>q = a - b\*p  
>     =>m也可以整除q  
>     =>m就是b和q的公约数  
>     =>n是b,q的最大公约数  
>     =>n <= m
> 2.  =>n 是q,b的最大公约数，那么n整除q,b  
>     =>a = b\*p + q  
>     =>n也可以整除a  
>     =>n就是b和a的公约数  
>     =>m是b,a的最大公约数  
>     =>m <= n

#### 思路分析： ####

Created with Raphaël 2.2.0输入a, br = mod(a, b) a = b b = rmod(a, b) = 0？输出ayesno

#### 代码实现： ####

#include<stdio.h>
        int Gcd(int M, int N)
        { 
            int Rem;
            while(N > 0)
            { 
                Rem = M % N;
                M = N;
                N = Rem;
            }
            return M;
        }
        int main(void)
        { 
            int a,b;
            scanf("%d %d",&a,&b);
            printf("the greatest common factor of %d and %d is ",a, b);
            printf("%d\n",Gcd(a,b));
            return 0;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关求最大公约数和最小公倍数---辗转相除法(欧几里得算法)

目录一.GCD和LCM 1.最大公约数 2.最小公倍数二.暴力求解 1.最大公约数 2.最小公倍数三.辗转相除法 1.最大公约数 2.最小公倍数 --

太过爱你忘了你带给我的痛/ 2024年03月25日 13:56/ 0 赞/ 46 阅读

相关辗转相除法求最大公约数

辗转相除法，也称为欧几里德算法，用于求两个非负整数的最大公约数（Greatest Common Divisor, GCD）。算法的基本思想是：假设有两个非负整数 a 和 b

Myth丶恋晨/ 2024年02月19日 07:41/ 0 赞/ 11 阅读

相关欧几里得算法（辗转相除法）

算法是程序的灵魂，不懂算法的程序员不是一个合格的程序员。源自LeetCode上的一道算法题，说实话，我已经忘记欧几里得算法是怎么实现的了。。。简介：欧几里得算法

迈不过友情╰/ 2023年07月13日 15:28/ 0 赞/ 81 阅读

相关欧几里德算法求最大公约数（辗转相除法）

//递归版本 include<stdio.h> int gcd(int a,int b) { if(b==0) {

r囧r小猫/ 2023年02月17日 06:19/ 0 赞/ 64 阅读

相关证明辗转相除法(欧几里德算法)

定理：两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。证明： gcd(

刺骨的言语ヽ痛彻心扉/ 2023年01月03日 14:28/ 0 赞/ 157 阅读

相关欧几里得算法(辗转相除法)--Java实现

欧几里得算法(辗转相除法)–Java实现版本一、非递归版本 static int gcd(int a,int b) { wh

迷南。/ 2022年10月28日 03:42/ 0 赞/ 121 阅读

相关求最大公约数-辗转相除法-欧几里德算法

这是一个 Python 写的求最大公约数的算法。 a = 12 b= 42 def find_divisor(a,b):

傷城~/ 2022年08月09日 12:45/ 0 赞/ 217 阅读

相关 JAVA实现辗转相除法欧几里得算法求逆

乘法逆元定义：一般来讲，如果要运算加法、减法、乘法、乘方，都应该满足以下式子： (a+b)%c=(a%c+b%c)%c(a+b)%c=(a%c+b%c)%c

Love The Way You Lie/ 2022年04月18日 05:38/ 0 赞/ 207 阅读

相关欧几里得算法(辗转相除法）求最大公约数代码

求解最大公约数依据如下定理：gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)；两个整数的最大公约数等于其中较小的那个数

短命女/ 2022年04月17日 05:07/ 0 赞/ 285 阅读

相关【算法】欧几里德算法(辗转相除法)求最大公约数

> 定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。 gcd(a,b) =

浅浅的花香味﹌/ 2022年04月10日 07:16/ 0 赞/ 157 阅读