（C++）求最大公因子（辗转相除法）

Bertha 。 2023-02-26 06:19 26阅读 0赞

具体算法也可以看这篇 ： [https://zhuanlan.zhihu.com/p/151447583][https_zhuanlan.zhihu.com_p_151447583]

求任意两个整数M,N最大公因子(M,N)的方法如下：

若 M=N\*Q+R        
其中：R为余数,　满足 0≤R≤N-1         
      则　(M,N)=(N,R)    
且当　R=0时， (M,N)=N  
按照这种方法，可以快速而方便地求出任意两个整数的最大公因子。    
例如，（1500，550）的求解过程如下：   
 （1500，550）=（550，400）  
=（400，150）=（150，100）  
=（100，50）=（50，0）=50   
最终求得1500和550的最大公因子为50。

### 非递归方式 ###

#include <iostream>
    using namespace std;
    
    int hcf(int m, int n)
    {
    	while (n!=0) {
    		int r = m % n;
    		m = n;
    		n = r; 
    	}
    	return m;
    }
    
    
    int main(int argc, char** argv) {
    	int a = hcf(1500, 550);
    	cout<<"最大公因数是："<<a; 
    	return 0;
    }

### 递归方式 ###

#include <iostream>
    using namespace std;
    
    int hcf(int m, int n)
    {
    	if (n==0) return m;
    	else return hcf(n, m % n); 
    }
    
    int main(int argc, char** argv) {
    	int a = hcf(1500, 550);
    	cout<<"最大公因数是："<<a; 
    	return 0;
    }

> 最大公因数是：50  
> \--------------------------------  
> Process exited after 0.1298 seconds with return value 0

[https_zhuanlan.zhihu.com_p_151447583]: https://zhuanlan.zhihu.com/p/151447583

发表评论取消回复

表情：

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

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

相关阅读

相关（C++）求最大公因子（辗转相除法）

具体算法也可以看这篇： [https://zhuanlan.zhihu.com/p/151447583][https_zhuanlan.zhihu.com_p_1514475

Bertha 。/ 2023年02月26日 06:19/ 0 赞/ 27 阅读

相关【青少年编程】求最大公约数的辗转相除法

> 「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入。如果加入了之前的社群不需要重复加入。 > > 我

拼搏现实的明天。/ 2022年09月16日 03:51/ 0 赞/ 210 阅读

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

描述：计算两个非负整数 p 和 q 的最大公约数：若 q 是 0，则最大公约数为 p。否则，将 p 除以 q 得到余数 r，p 和 q 的最大公约数即为 q 和 r 的最大公约

向右看齐/ 2022年08月21日 06:43/ 0 赞/ 260 阅读

相关辗转相除法，辗转相减法，枚举法实现最大公约数的计算 && 求最小公倍数

题目：最大公约数和最小公倍数计算。从键盘接收两个整数，编写程序求出这两个整数的最大公约数和最小公倍数 (提示:求最大公约数可用辗转相除法，求最小公倍数的积除以最大公约数即

今天药忘吃喽~/ 2022年04月23日 23:10/ 0 赞/ 272 阅读

相关 C语言实现大整数的辗转相除法

辗转相除法，原理，先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这

冷不防/ 2022年03月31日 14:52/ 0 赞/ 301 阅读

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

主要是依据扩展欧几里德算法中gcd(a,b)=gcd(b,a mod b) 数学证明过程：（参考百科） ![在这里插入图片描述][watermark_type_ZmFu

青旅半醒/ 2022年03月09日 00:05/ 0 赞/ 261 阅读

相关 C实现辗转相除法

目标：求最大公约数方法：利用欧几里得算法（辗转相除法）思路：如果b=0,计算结束，a就是最大公约数否则，计算a除以b的余数，让a=b，而b=余数；回到第一步。

痛定思痛。/ 2022年02月15日 05:43/ 0 赞/ 224 阅读

相关 C语言。求两个数的最大公约数，最小公倍数，辗转相除法

辗转相除法求两个数的最大公约数辗转相除法，又名[欧几里德算法][Link 1]（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用

迈不过友情╰/ 2022年01月22日 06:49/ 0 赞/ 278 阅读

相关最小公倍数 //辗转相除法

include<stdio.h> include<string.h> void swap(int &x,int &y) { int

- 日理万妓/ 2021年11月02日 14:40/ 0 赞/ 370 阅读

相关辗转相除法

问题：给出两个数a和b，求出他们的最大公约数(greatest common divisor)。解法一：辗转相除法，又叫欧几里得算法。两个正整数a和b（a>b），他们的最大

不念不忘少年蓝@/ 2021年10月29日 09:50/ 0 赞/ 333 阅读