C语言入门——求最大公约数（2种方法超详细）-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言入门——求最大公约数（2种方法超详细）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基本介绍：
最大公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个。

最大公约数
能够整除一个整数的整数称为其的约数（如5是10约数）；
能够被一个整数整除的整数称为其的倍数（如10是5的倍数）；
如果一个数既是数A的约数，又是数B的约数，称为A,B的公约数，A,B的公约数
中最大的一个（可以包括AB自身）称为AB的最大公约数

定义：
如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

例：在4、6中， 2就是4，6的最大公约数.

法一：枚举

1.设t为2;
2.如果 u 和 v 都能被 t 整除，则记下这个 t ；
3. t 加 1 后重复第2步，直到t等于u 或 v ;
4.那么，曾经记下的最大的可以同时整除 u 和 v 的 t 就是 gcd；

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
	int a, b,i;
	scanf("%d %d", &a, &b);
	int min,ret=0;
	for (i = 1; i < (min = a < b ? a : b); i++)
	{
		if (a % i == 0 && b % i == 0)
			ret = i;
	}
	printf("%d和%d的最大公约数是%d", a, b, ret);
	return 0;
}

输入： 4和6 看下结果

C语言入门——求最大公约数（2种方法超详细）

法二：辗转相除法

1.如果b等于0，计算结束，a就是最大公约数;

2.否则，计算a除以b的余数，让a等于b，而b等于那个余数;

3.回到第一步。

例如：4 % 6 a=6 b=4

6%4 a=4 b=2

4%2 a=2 b=0

所以4和6最大公约数为2。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
	int a, b;
	int t;
	scanf("%d %d", &a, &b);
	while(b!=0)
	{
		t = a % b;
		a = b;
		b = t;
	}
	printf("gcd=%d", a);
	return 0;
}

这时肯定有人要问最小公倍数

tip：最小公倍数等于两数之积除以其最大公约数

只需要定义一个变量（最小公倍数）= (a * b) / gcd文章来源地址https://www.toymoban.com/news/detail-482155.html

到了这里，关于C语言入门——求最大公约数（2种方法超详细）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！