目录

原题一：求最大公约数

方法一：暴力求解

方法二：辗转相除法（很重要哦）

原题二：最小公倍数

方法一：暴力求解

方法二：利用最大公约数

结语

【前言】

今天是刷题打卡第32天！

加油吧少年。

原题一：求最大公约数

方法一：暴力求解

思路：

举一个例子，比如求24和18的最大公约数，它再大，也不可能比18还大，所以先假设最大公约数是18，看18能不能把24和18都整除掉，不能的话就减一，最后就能得到答案，emmm，这个方法很暴力，效率很低，大家简单看一下就行了。

代码执行：

//方法一：暴力求解法
#include<stdio.h>

int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	//求m和n的较小值，假设较小值就是最大公约数
	int ret = (m < n) ? (m) : (n);
	while (1)
	{
		if ((m % ret == 0) && (n % ret == 0))
		{
			break;
		}
		ret--;
	}
	printf("%dn", ret);
	return 0;
}

方法二：辗转相除法（很重要哦）

怎么说呢，当余数等于0的时候，除数就是最大公约数 。有个好处就是不需要判断M和N的大小！

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

int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	int ret = 0;
	while (ret = m % n)
	{
		m = n;
		n = ret;
	}
	printf("%dn", n);
	return 0;
}

递归实现辗转相除法：

//辗转相除法（递归写法）
#include<stdio.h>

int gcd(int m, int n)
{
	if (n == 0)
		return m;
	return gcd(n, m % n);
}

int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	int ret = gcd(m, n);
	printf("%dn", ret);
	return 0;
}

原题二：最小公倍数

方法一：暴力求解

思路：

举一个例子，比如求24和18的最小公倍数，它再小，也不可能比24还小，所以先假设最小公倍数是24，看24和18能不能把24整除掉，不能的话就加一，最后就能得到答案，emmm，这个方法很暴力，效率很低，大家简单看一下就行了。

代码执行：

//方法一：暴力求解法
#include<stdio.h>

int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	int ret = (m > n) ? (m) : (n);
	while (1)
	{
		if ((ret % m == 0) && (ret % n == 0))
		{
			break;
		}
		ret++;
	}
	printf("%dn", ret);
	return 0;
}

方法二：利用最大公约数

思路：

假如两个数m和n，最大公约数为a，最小公倍数 == m * n / a

代码执行：

//方法二：利用最大公约数
#include<stdio.h>

int gcd(int m, int n)
{
	//找递归边界
	if (n == 0)
		return m;
	return gcd(n, m % n);
}

int main()
{
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	int ret = gcd(m, n);//最大公约数
	int s = m * n;
	printf("%dn", s / ret);
	return 0;
}

结语

今天是刷题打卡第32天！

加油吧少年。