关键字挖掘机爱站网,wordpress 企业站开发,陕西交通建设集团网站体检,网页qq登录不了怎么回事前言 对于初学编程的小伙伴们肯定经常遇见此类问题#xff0c;而且为之头疼#xff0c;今天我来给大家分享一下#xff0c;最大公因数和最小公倍数的求法。让我们开始吧#xff01; 文章目录 1#xff0c;最大公因数法1法2法3 2#xff0c;最小公倍数3#xff0c;尾声 …前言 对于初学编程的小伙伴们肯定经常遇见此类问题而且为之头疼今天我来给大家分享一下最大公因数和最小公倍数的求法。让我们开始吧 文章目录 1最大公因数法1法2法3 2最小公倍数3尾声 1最大公因数
首先提起最大公因数大家最先想到的就是辗转相除法。 假如求ab的最大公因数x。其中ab。a可以表示为nbt,那么ta-nb,因为x是a和b的公因数将等式两边同时除以x得t/xa/x-n*b/x,那么我肯可以知道t/x是个整数所以x是a和a%b的公因数那么我们可知那么x也是b和a%b的公因数。所以a和b的最大公约数和b和a%b的最大公约数是一样的。那么我们就可以使用循环的方法求出最大公因数如下
法1
#includestdio.h
int gcd(int a, int b)
{if (a b)//判断大小事大数除以小数{int temp a;a b;b temp;}while (a % b)//辗转相除{int temp a;a b;b temp%b;}
}
int main()
{int a, b;scanf(%d %d, a, b);int ans gcd(a,b);printf(%d, ans);return 0;
}那么这样写有点麻烦我们可以直接使用递归的方法解决而且速度更快。
法2
#includestdio.h
int gcd(int a, int b)
{if (a 0)//当a为0时b为最大公因数return b;return gcd(b, a%b);
}
int main()
{int a, b;scanf(%d %d, a, b);int ans gcd(a,b);printf(%d, ans);return 0;
}那么有没有更快的方法呢当然有我们都知道位运算的速度比除法运算快的多那么我肯可以吧代码改成这样。
法3
#includestdio.h
int gcd(int a, int b)
{while (b ^ a ^ b ^ a % b);//连等式是从右往左计算的我们要知道a^a0,a^0a。那么连等式就可以等同于gcdb,a%breturn a;
}
int main()
{int a, b;scanf(%d %d, a, b);int ans gcd(a,b);printf(%d, ans);return 0;
}这种算法是最快的
2最小公倍数
正常求法求最小公倍数可能太过麻烦但是我们要知道一个定理。假设x是a和b的最大公因数y是a和b的最小公倍数那么xyab。如果不明白可以百度一下或者直接背下来当结论用 所以我们就可以用上面的方法先求出x然后再用ya*b/x求出y的值。
3尾声
本期的分享到这里结束如果觉得博主讲的不错的话请给博主一个点赞一个收藏支持一下我们下期再见
