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

迈不过友情╰ 2022-01-22 06:49 277阅读 0赞

# 辗转相除法求两个数的最大公约数 #

辗转相除法， 又名[欧几里德算法][Link 1]（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

## 基本原理 ##

两个数的最大公约数是指能同时整除它们的最大正整数。

设两数为a、b(a≥b)，求a和b最大公约数 ![format_png][] 的步骤如下：

(1)用a除以b(a≥b)，得 ![format_png 1][] 。

(2)若 ![format_png 2][] ，则 ![format_png 3][] ；

(3)若 ![format_png 4][] ，则再用b除以 ![format_png 5][] ，得 ![format_png 6][] .

(4)若![format_png 7][] ，则 ![format_png 8][] ；若 ![format_png 9][] ，则继续用 ![format_png 10][] 除以 ![format_png 11][] ，......，如此下去，直到能整除为止。其最后一个余数为0的除数即为 ![format_png 12][] 的最大公约数。

## 证明 ##

设两数为a、b(a>b)，用 ![format_png 13][] 表示a，b的[最大公约数][Link 2]，r=a (mod b) 为a除以b的余数，k为a除以b的商，即 ![format_png 14][] 。

辗转相除法即是要证明 ![format_png 15][] 。

第一步：令 ![format_png 16][] ，则设 ![format_png 17][]

第二步：根据前提可知 ![format_png 18][]

第三步：根据第二步结果可知，![format_png 19][] 也是 ![format_png 20][] 的因数

第四步：可以断定 ![format_png 21][] 与 ![format_png 22][] [互质][Link 3]（这里用[反证法][Link 4]进行证明：设 ![format_png 23][] ，则

![format_png 24][] ，

则![format_png 25][] ，则a与b的一个公约数 ![format_png 26][] ，

故c非a与b的最大公约数，与前面结论矛盾，因此c也是b与r的最大公约数）从而可知

![format_png 27][] ，继而![format_png 28][] 。

证毕

注：以上步骤的操作是建立在刚开始时 ![format_png 29][] 的基础之上的，即m与n亦互质。

#include<stdio.h>
    
    int GCD(int a,int b);
    
    int main(){
    	int a,b,gcd;
    	scanf("%d%d",&a,&b);
    	gcd=GCD(a,b); 
    	printf("GCD=%d\n",gcd);
    	printf("LCM=%d\n",a*b/gcd);
        return 0;
    }
    
    
    int GCD(int a,int b){
    	int n;
    	n=b;
    	while(n!=0){
    		n=a%b;
    		if(n!=0) {
    		a=b;
    		b=n;
    		}
    	}
    	return b;
    }

一般方法

#include<stdio.h>
    int gcd( int x, int y );
    int main(){
    	int a,b,gcd;
    	scanf("%d%d",&a,&b);
    	gcd=GCD(a,b); 
    	printf("GCD=%d\n",gcd);
    	printf("LCM=%d\n",a*b/gcd);
        return 0;
    }
    
    int gcd( int x, int y ){
    	int t,i;
    	for(i=1;i<y+1;i++)
    	if(x%i==0&&y%i==0) t=i;
    	return t;
    }

[Link 1]: https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%B7%E7%AE%97%E6%B3%95/9002848
[format_png]: /images/20220122/e568a4993c5243c2ab39226958abaf8b.png
[format_png 1]: /images/20220122/69579fb6d3714199989095d134e3b01a.png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MzLmJkc3RhdGljLmNvbS83UG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDQxL3NpZ249NzlkNjQyNmYwMDdiMDIwODA4YzkzZWUwNjBkOTg4ZmEvMjAzZmI4MGU3YmVjNTRlNzIxMDE3MGQ0YjMzODliNTA0ZWMyNmEwZS5qcGc?x-oss-process=image/format,png
[format_png 3]: /images/20220122/c5321f1c970e4c088f6d82fc95de41a0.png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS85dm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDQzL3NpZ249NTAzNjY2MjFiY2ZkNTI2NmEzMmIzZDE3YTkxODRlYWIvNDIxNjZkMjI0ZjRhMjBhNDk3ZGU1NjBkOWE1Mjk4MjI3MzBlZDAzYy5qcGc?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS85Zm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDEyL3NpZ249MDczODZjMmQ5YjIzOTdkZGQyNzk5YzA2NTg4MmRmYTkvYzlmY2MzY2VjM2ZkZmMwM2YwNDViNjcyZGUzZjg3OTRhNGMyMjYzZS5qcGc?x-oss-process=image/format,png
[format_png 6]: /images/20220122/215099c3e7ac417ca9b78674ebf890c3.png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS8tdm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDQxL3NpZ249NzhiMWNlYWJmOWRlYjQ4ZmZmNjlhMGRmZjExZjM4NzcvZDAxMzczZjA4MjAyNWFhZjIxNDQyYTAxZjFlZGFiNjQwMjRmMWE4MS5qcGc?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MzLmJkc3RhdGljLmNvbS8tUG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDYzL3NpZ249MDhhMjM1MWQzY2QxMmYyZWNhMDVhZDYzNGVjMjI4N2EvYjdmZDUyNjZkMDE2MDkyNGQ4NTZmNmQxZGUwNzM1ZmFlN2NkMzQ4Yy5qcGc?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MzLmJkc3RhdGljLmNvbS83UG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDQzL3NpZ249MTNlZmVjZWEwYmU5MzkwMTUyMDI4YzNkN2FlYzJlNjIvZGNjNDUxZGE4MWNiMzlkYmQ5Y2IzMzljZGExNjA5MjRhYTE4MzBmNC5qcGc?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MzLmJkc3RhdGljLmNvbS8tUG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDEyL3NpZ249MDM4MDljZTU0YjM0OTcwYTQzNzMxNDJkOTRjYTE1N2UvODYwMWExOGI4N2Q2Mjc3ZjM1N2M2NmYyMjIzODFmMzBlODI0ZmM4YS5qcGc?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MwLmJkc3RhdGljLmNvbS8tNG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDEzL3NpZ249NzIwNzY4MGQ5YTUyOTgyMjAxMzMzZGMwZDZjYWVjNGMvMzVhODVlZGY4ZGIxY2IxMzdkNzA2OGQ5ZDc1NDU2NGU5MzU4NGJkYS5qcGc?x-oss-process=image/format,png
[format_png 12]: /images/20220122/a9d5f6914c6e469d96603fed98366499.png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS85Zm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDYwL3NpZ249ZGJjZGNhZTI5ZDJiZDQwNzQ2YzdkMGZkNzk4OTQ5OTIvMjFhNDQ2MjMwOWY3OTA1MjRhY2IxM2Y0MDZmM2Q3Y2E3YWNiZDUyMC5qcGc?x-oss-process=image/format,png
[Link 2]: https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0
[format_png 14]: /images/20220122/44295343152d43ef911859e63ec243ba.png
[format_png 15]: /images/20220122/1bd3f9e2001841d3b41c48c4d26f96bd.png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MwLmJkc3RhdGljLmNvbS85NG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDg1L3NpZ249NDI1MzZlMDlkZGNhN2JjYjc5N2JjYTJhYmYwOWU4MDkvOTgyNWJjMzE1YzYwMzRhODZlODJlZjRiYzExMzQ5NTQwODIzNzY5My5qcGc?x-oss-process=image/format,png
[format_png 17]: /images/20220122/af992ba2d93b4eb9a045fb0816d191d1.png
[format_png 18]: /images/20220122/c0b6cb37ee1848f3a5864f17d3b7ce2d.png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS85Zm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDgvc2lnbj1jMzQ2ZDFlMWJhNTFmODE5ZjUyNTBlN2JkYWU2YmIvZmFmMmIyMTE5MzEzYjA3ZTMwZDQwN2MyMDZkNzkxMjM5NmRkOGM4Yi5qcGc?x-oss-process=image/format,png
[format_png 20]: /images/20220122/800320a751e748fba54936508490c488.png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS85Zm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDQ3L3NpZ249NGI5MWQxMjQ5NjgyZDE1OGJmODI1OGI2ODIwYTAyYzQvYjgwMTRhOTBmNjAzNzM4ZDMzZWY1YmU4YjkxYmIwNTFmOTE5ZWM1Ny5qcGc?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MzLmJkc3RhdGljLmNvbS83UG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDkvc2lnbj04ZWVjYzIxNjAyZmE1MTNkNTVhYTYwZWYzZGMwYWQvZTRkZGU3MTE5MGVmNzZjNmI4OGNhY2UxOTcxNmZkZmFhZTUxNjc5OS5qcGc?x-oss-process=image/format,png
[Link 3]: https://baike.baidu.com/item/%E4%BA%92%E8%B4%A8
[Link 4]: https://baike.baidu.com/item/%E5%8F%8D%E8%AF%81%E6%B3%95
[format_png 23]: /images/20220122/cf846bce4eb04f2fa6126c4021745c9e.png
[format_png 24]: /images/20220122/93dcc1359fed405a8fcf2803b0d06e59.png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MzLmJkc3RhdGljLmNvbS8tUG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDIyOC9zaWduPTQ4ZGVhYTEwMWZjZTM2ZDNhNjA0ODQzMjAyZjIzYTI0LzIwM2ZiODBlN2JlYzU0ZTcyNWJhNGNkNGIzMzg5YjUwNGVjMjZhYTEuanBn?x-oss-process=image/format,png
[format_png 26]: /images/20220122/26d6ee22760e4e5e982fe921bdd013f1.png
[format_png 27]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MzLmJkc3RhdGljLmNvbS83UG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDg0L3NpZ249ODIwZmNjYWJmOWRlYjQ4ZmZmNjlhY2RhZjIxZjM4YTIvZDgzM2M4OTVkMTQzYWQ0YmFlZTYxMDBhODgwMjVhYWZhNTBmMDYyYi5qcGc?x-oss-process=image/format,png
[format_png 28]: /images/20220122/483a163197934d479d2052debcdf7aca.png
[format_png 29]: /images/20220122/8d39e88ec0dc4f92b15e35b40fce8269.png