求最大公约数

请添加图片描述

本期介绍🍖
主要介绍：求两数的最大公约数，通过辗转相除法计算。

文章目录

1. 求最大公约数
2. 遍历法
3. 辗转相除法

1. 求最大公约数

题目：给定两个数，求这两个数的最大公约数。
最大公约数：指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。举个例子：18和24的最大公约数是6。

2. 遍历法

思路：从1开始试除，直到给定两个数中较小的那个值。如果存在能够同时整除两个数的数，则该数就是公约数。随着试除的继续，公约数不断更新迭代，最后试除结束前的那个公约数就是最大公约数。代码如下：

#include<stdio.h>

int main()
{
	int num1 = 0;
	int num2 = 0;
	scanf("%d %d", &num1, &num2);
	int min = 0;
	int com_max = 1;//最大公约数
	//找出输入两个数中较小的那个
	if (num1 < num2)
		min = num1;
	else
		min = num2;
	//找最大公约数
	int i = 0;
	for (i = 1; i <= min; i++)
	{
		//公约数判断条件
		if ((num1 % i == 0) && (num2 % i == 0))
		{
			com_max = i;
		}
	}
	printf("最大公约数是：%d\n", com_max);
	return 0;
}

在这里插入图片描述

3. 辗转相除法

辗转相除法又称欧几里得算法，是指用于计算两个非负整数a，b的最大公约数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。代码如下：

//辗转相除法
#include<stdio.h>

int main()
{
	int num1 = 0;
	int num2 = 0;
	int r = 0;
	int com_max = 0;
	scanf("%d %d", &num1, &num2);
	//如果被除数和除数的余数为0，则除数就是最大公约数
	//如果被除数和除数的余数不为0，则以除数为被除数，余数为除数，计算余数。
	while ((r = num1 % num2) != 0)
	{
		num1 = num2;
		num2 = r;
	}
	com_max = num2;
	printf("最大公约数：%d\n", com_max);
	return 0;
}