前言
我們在C語言的學(xué)習(xí)中，經(jīng)常會遇到這樣一些數(shù)學(xué)題目，良好掌握這些題目有利于我們理解和學(xué)習(xí)C語言，話不多說，直接進(jìn)入主題
什么是最大公約數(shù)和最小公倍數(shù)
最大公約數(shù)：
首先我們舉個例子，比如12 和16，12的約數(shù)有（1,2 ,3,4,6,12）,16的約數(shù)有（1,2,4,8,16）公約數(shù)就是兩個數(shù)共同的約數(shù)，（1,2,4）而公約數(shù)中最大的就是最大公約數(shù)。
最小公倍數(shù)
我們同樣舉個例子，比如12和16，我們將163=48,124=48，這是兩個數(shù)第一次有倍數(shù)相等關(guān)系，就叫48是最小公倍數(shù)
最大公約數(shù)與最小公倍數(shù)的公式
最大公約數(shù) —— Greatest Common Divisor(GCD)
最小公倍數(shù) —— Leatest Common Multiple(LCM)
假設(shè)a和b是我們已知的數(shù)，那么 就存在一個公式。
公式展示
a ? b = G C D ? L C M a*b=GCD*LCM a?b=GCD?LCM
這與我們的路程公式很相似，我們可以類比記憶，路程=速度*時間
所以我們只要求出其中的一個就行，求出GCD 就可以通過公式求出LCM，
求出LCM就可以通過公式求出GCD。
求最大公約數(shù)方法
方法一：暴力窮舉法
細(xì)節(jié)講解： 我們知道最大公約數(shù)是約數(shù)中能同時整除兩數(shù)，并且是最先整除的，那我們就可以一個一個試。我們可以將l兩個數(shù)中小的那個賦給tmp,為什么呢？因?yàn)槲覀冋易畲蠊稊?shù)時最大也不會超過a,b兩個數(shù)中最小的那個。
比如16 和12 ，我們肯定是從12往下找，而不是還要在16~12之間浪費(fèi)時間。 我們來看看代碼
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int tmp = a > b ? b : a;
while (1)
{
if (a % tmp == 0 && b % tmp == 0)
{
printf("最大公約數(shù)是%d", tmp);
break;
}
else
tmp--;
}
return 0;
}
方法二：輾轉(zhuǎn)相除法
在數(shù)學(xué)中，輾轉(zhuǎn)相除法，又稱歐幾里得算法（Euclidean algorithm），是求取最大公約數(shù)的一種算法。輾轉(zhuǎn)相除法首次出現(xiàn)于歐幾里得的《幾何原本》中的第Ⅶ卷，書中的命題ⅰ和命題ⅱ所描述的就是輾轉(zhuǎn)相除法，而在中國，輾轉(zhuǎn)相除法最早出現(xiàn)在《九章算法》中。可以說這是一個非常經(jīng)典的方法
我們來看流程圖
解析：如果我們有a,b a = 24 b = 18 ,我們先讓 24 % 18 = 6 ，
接下來我們讓 18 % 6 = 0 ；剛好符合我們流程圖中藍(lán)色框框的條件，這樣就能確定 6 就是最大公倍數(shù)。如果是18 % 24 呢？
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
while (1)
{
int c = a % b;
if (0 == a % b)
{
printf("%d就是最大公約數(shù)", b);
break;
}
else
{
a = b ;
b = c;
}
}
return 0;
}
方法三：更相減損術(shù)
《九章算術(shù)》是中國古代的數(shù)學(xué)專著，其中的“更相減損術(shù)”可以用來求兩個數(shù)的最大公約數(shù)
流程圖：
用更相減損術(shù)求98與63的最大公約數(shù)。
我們只要跟著流程圖走，然后一直改變 a 和 b 的值然后直至a b 相等就行,a b 相等時的那個數(shù)就是最大公倍數(shù)，下面給出代碼
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
while (1)
{
if (a == b)
{
printf("最大公倍數(shù)是%d", a);
break;
}
if (a > b)
{
a = a - b;
}
if (b > a)
{
b = b - a;
}
}
return 0;
}
求最小公倍數(shù)的方法
方法一：公式法
a ? b = G C D ? L C M a*b=GCD*LCM a?b=GCD?LCM
所以我們只要求出其中的一個就行，求出GCD 就可以通過公式求出LCM，
我們上面已經(jīng)介紹了三種求GCD的方法，直接用公式也是可以的。
方法二：暴力窮舉法
我們知道最小公倍數(shù)就是能夠同時整除我們已知的兩個數(shù)的數(shù)，而且我們可以從兩個數(shù)中更大的開始，比如說求45和30的最小公倍數(shù)。
我們肯定是從45 往上找。
由于方法比較暴力我們就直接看代碼吧！
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int c = a > b ? a : b;
while (1)
{
if (0 == c % a && 0 == c % b)
{
printf("最小公倍數(shù)是%d", c);
break;
}
c++;
}
return 0;
}
方法三：疊乘法
方法講解：
已知兩個數(shù)的公倍數(shù)一定與這兩個數(shù)存在倍數(shù)關(guān)系，那么求解最小公倍數(shù)我們就可以將其中一個數(shù)依次擴(kuò)大1倍、2倍、3倍……直到出現(xiàn)第一個擴(kuò)大n倍的數(shù)可以同時整除這兩個數(shù)，這個數(shù)就是最小公倍數(shù)。
計算36和270的最小公倍數(shù)
我們直接給出代碼
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int i = 1;
while (a * i % b != 0)
{
i++;
}
printf("最小公倍數(shù)是%d", a * i);
return 0;
}
最后總結(jié)
通過這篇博客我們知道了求最大公約數(shù)和最小公倍數(shù)的許多方法，當(dāng)然不止這些方法，但是我覺得這些應(yīng)該夠用一段時間了。我是一個博客新手，本文若是有筆誤之處，請大家多多指出。最后寫博客是一件很辛苦但是很有成就感的一件事情。文章來源：http://www.zghlxwxcb.cn/news/detail-761810.html
這篇文章到這里就結(jié)束了，如果有幫到你就請點(diǎn)個贊吧。我的博客是不添加水印的，大家也可以用里面的圖片。最后就麻煩用你的小手點(diǎn)個贊吧，哈哈Thanks?(?ω?)?
文章來源地址http://www.zghlxwxcb.cn/news/detail-761810.html
到了這里，關(guān)于【C語言】一篇博客帶你弄懂最大公約數(shù)和最小公倍數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
