[数据结构与算法]C语言练习——求两个数的最大公约数（三种算法）

给定两个整数，让你求这两个数的最大公约数

最大公约数顾名思义就是：这几个整数共有的约数中最大的一个。

目录

1. 辗转相除法

2.更相减损法

3.穷举法?

1. 辗转相除法

思路：

（1）将两个整数求余数a%b = c；如果c = 0，则b为最大公约数

（2）如果c != 0，则让a = b, b = c，继续执行a%b = c；判断条件为c是否为零

例如：a = 15，b = 18

c = a%b = 15%18 = 15，c = 15,c此时不等于0；

则进行a = b，b = c；a = 18，b = 15；

继续执行c = a%b = 18%15 = 3，此时c=3不为0；

执行a = b， b = c；a = 15，b = 3；

继续进行c = a%b = 15%3 = 0；此时c = 0循环结束。

代码如下：

#include<stdio.h>
int main()
{
	int a, b, c;
	printf("请输入两个整数：");
	scanf("%d%d", &a, &b);
	c = a % b;
	while (c != 0)
	{
		a = b;
		b = c;
		c = a % b;
	}
	printf("最大公约数为:%d", b);
	return 0;
}

2.更相减损法

思路：

（1）如果a = b；则a或b就是最大公约数

（2）如果a != b；若a>b，则a = a-b；若a<b，则b = b-a；一直执行到a = b循环结束

例如：a = 15，b = 18

因为a != b且a<b，则b = a-b = 18-15 = 3，

b = 3，a>b，则a = a-b = 15-3 = 12 ，

a = 12，a>b，则a = a-b =12-3 = 9，

a = 9，a>b，则a = a-b =9-3?= 6，

a = 6，a>b，则a = a-b =6-3 = 3，

a = 3，a = b = 3，此时a = b = 3循环结束。

代码如下：

#include <stdio.h>
int main()
{
	int a, b;
	printf("请输入两个整数：");
	scanf("%d %d", &a, &b);
	while (a != b)
	{
		if (a > b)
			a = a - b;
		else
			b = b - a;
	}
	printf("最大公约数为：%d\n", a);

	return 0;

}

3.穷举法?

思路：

（1）选出a和b最小的数放入c中，然后分别用a和b对c求余数，看是否能被c整除，同时能被c整除则c是这两个数的最大公约数

（2）如果不能被c同时整除，c进行减一（c--）,一直执行到a和b同时能被c整除。

例如：a = 15，b = 18

把较小值赋给c，c = 15，a%c = 15%15 = 0，b = b%c = 18%15 = 3,不能同时被c整除，循环继续 c--；

a%c = 15%14?= 1，b = b%c = 18%14 = 4,不能同时被c整除，循环继续 c--；

....（不一一列举了）

a%c = 15%3?= 0，b = b%c = 18%3?= 0,能同时被c整除，循环结束。

代码如下：

#include<stdio.h>  
int main()
{

	int a, b;
	int c = 0;
	printf("请输入两个整数：");
	scanf("%d %d", &a, &b);
	c = (a > b) ? b : a;   //三目运算符 将最小的赋给c
	while (a % c != 0 || b % c != 0)    
	{
		c--;
	}
	printf("最大公约数为：%d\n", c);

}

最后，文章结束啦！！