C语⾔编程题 计算最⼤公约数 和 打印最⼩公倍数

1. 计算最⼤公约数

1.1 题⽬描述：

      输⼊2个整数m和n，计算m和n的最⼤公约数，并打印出结果

2.2 解法思路：

       最⼤公约数是指两个或多个整数共有约数中最⼤的⼀个。为了求出两个数的最⼤公约数，可以采⽤:

 •枚举试除法：

 1. 具体来说，公约数⼀定⼩于两个数，从两个数中的较⼩值开始枚举；

 2. 从⼤到⼩依次判断能否同时整除这两个数，若某个数满⾜同时整除两个数，则其为公约       数；

3. 从⼤到⼩遍历找到公约数时，此数即为最⼤公约数，此时应当结束循环。

#include<stdio.h>
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	//计算找出m和n的较小值k
	//因为最⼤公约数最⼤是m和n的较⼩值
	int k = (m > n ? n : m); //三目操作符 m>n为真 则返回n  为假 则返回m
	while (1)
	{
		if (m % k == 0 && n % k == 0)
		{
			break;
		}
		k--;
	}
	printf("%d\n", k);
	return 0;
}

• 辗转相除法：

 辗转相除法也称为欧⼏⾥得算法，是⼀种⽤来求两个正整数最⼤公约数的⽅法。它基于⼀个  简单的数 学原理：如果 a 和 b 是两个正整数，且 a>b ，则a和b的最⼤公约数等于 b 和 a%b （ a 除以 b 所得的余数）的最⼤公约数。

辗转相除法的步骤如下：

1. 如果 a<b，将 a 和 b 交换。

2. 如果 a除以b，得到商q和余数r，即a=bq+r。

3.如果r等于0，则b就是最大公约数。

4.如果r不等于0，则再用b除以r，得到商q1和余数r1，即b=rq1+r1。

5.重复步骤3和步骤4，直到余数等于0为⽌。

6. 最后的除数就是两个数的最⼤公约数。

解法代码:

#include<stdio.h>
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	int k = 0;
	while (k = m % n)
	{
		m = n;
		n = k;
	}
	printf("%d\n", n);
	return 0;
}

2.打印最⼩公倍数

2.1 题⽬描述：

       输⼊2个整数m和n，计算m和n的最⼩公倍数，并打印出结果

2.2 解法思路:

最⼩公倍数是指两个或多个整数共有倍数中最⼩的⼀个。为了求出两个数的最⼩公倍数，可以采⽤:

 •枚举试除法： 

1. 公倍数⼀定⼤于两个数，从两个数中的较⼤值开始枚举；

2. 从⼩到⼤依次判断能否同时整除这两个数，若某个数满⾜同时被两个数整除，则其为公倍数；

3. 从⼩到⼤遍历找到公倍数时，此数即为最⼩公倍数，此时应当结束循环；

• 特别地，最⼩公倍数可以由两数乘积除以两数的最⼤公约数求得。

解法代码:

解法一:

#include<stdio.h>
int main()
{
	int m = 0;
	int n = 0;
	//计算m和n的较⼤值
	//m和n的最⼩公倍数，最⼩也是m和n中较⼤的值
	scanf("%d %d", &m, &n);
	int k = (m > n ? m : n);
	while (1)
	{
		if (k % m == 0 && k % n == 0)
		{
			printf("%d\n", k);
			break;
		}
		k++;
	}
	return 0;
}

解法二：

#include<stdio.h>
int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	int k = 0;
	int mul = m * n;
	//辗转相除法求得最⼤公约数
	while (k=m%n)
	{
		m = n;
		n = k;
	}
	printf("%d\n", mul / n);
	return 0;
}