【手把手带你刷好题】—— 32.求最大公约数+求最小公倍数
【摘要】
目录
原题一：求最大公约数
方法一：暴力求解
方法二：辗转相除法（很重要哦）
原题二：最小公倍数
方法一：暴力求解
方法二：利用最大公约数
结语
【前言】
今天是刷题打卡第32天！
加油吧少年。
原题一：求最大公约数
方法一：暴力求解
思路：
举一个例子，比如求24和18的最大公约数，它...
目录
【前言】
今天是刷题打卡第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("%d\n", 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("%d\n", 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("%d\n", 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("%d\n", 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("%d\n", s / ret);
-
return 0;
-
}
结语
今天是刷题打卡第32天！
加油吧少年。
文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。
原文链接：bit-runout.blog.csdn.net/article/details/121598355
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）