C語言輾轉(zhuǎn)相除法求2個(gè)數(shù)的最小公約數(shù)
輾轉(zhuǎn)相除法最大的用途就是用來求兩個(gè)數(shù)的最大公約數(shù)。
用（a,b）來表示a和b的最大公約數(shù)。
有定理： 已知a,b,c為正整數(shù)，若a除以b余c，則（a,b）=(b,c)。 （證明過程請(qǐng)參考其它資料）
例：求 15750 與27216的最大公約數(shù)。
解：
∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466）
∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284)
∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898）
∵4284=2898×1+1386 ∴（4284，2898）=（2898，1386）
∵2898=1386×2+126 ∴（2898，1386）=（1386，126）
∵1386=126×11 ∴（1386，126）=126
所以（15750，27216）=126
輾轉(zhuǎn)相除法比較適合用來求兩個(gè)比較大的數(shù)的最大公約數(shù) 。
代碼如下：
#include<stdio.h>
int main()
{
int a,b,temp,x;
scanf("%d%d",&a,&b);
if(a>b)
{
temp=b;
b=a;
a=temp;
}
while(b%a!=0)
{
x=b%a;
b=a;
a=x;
}
printf("%d",a);
}
以上所述是小編給大家介紹的C語言輾轉(zhuǎn)相除法求2個(gè)數(shù)的最小公約數(shù)，希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
相關(guān)文章
C++實(shí)現(xiàn)LeetCode(116.每個(gè)節(jié)點(diǎn)的右向指針)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(116.每個(gè)節(jié)點(diǎn)的右向指針),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++求1到n中1出現(xiàn)的次數(shù)以及數(shù)的二進(jìn)制表示中1的個(gè)數(shù)
這篇文章主要介紹了C++求1到n中1出現(xiàn)的次數(shù)以及數(shù)的二進(jìn)制表示中1的個(gè)數(shù),兩道基礎(chǔ)的算法題目,文中也給出了解題思路,需要的朋友可以參考下2016-02-02
這篇文章主要介紹了C++ 迷宮游戲?qū)崿F(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了詳解C語言中的常量指針和指針常量,包括其之間的區(qū)別是C語言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-08-08
這篇文章主要介紹了利用Qt實(shí)現(xiàn)的一個(gè)文本編輯器。本文將具體講解下是如何實(shí)現(xiàn)菜單欄以及工具欄上對(duì)應(yīng)的需求，感興趣的可以動(dòng)手試一試2022-01-01
詳解C++中十六進(jìn)制字符串轉(zhuǎn)數(shù)字（數(shù)值）
這篇文章主要介紹了詳解C++中十六進(jìn)制字符串轉(zhuǎn)數(shù)字（數(shù)值）的相關(guān)資料,這里提供兩種實(shí)現(xiàn)方法，需要的朋友可以參考下2017-08-08
這篇文章主要介紹了C++ 實(shí)現(xiàn)輸入含空格的字符串，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-12-12
opencv3/C++ 將圖片轉(zhuǎn)換為視頻的實(shí)例
今天小編就為大家分享一篇opencv3/C++ 將圖片轉(zhuǎn)換為視頻的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-12-12
這篇文章主要為大家家詳細(xì)介紹了可讀可執(zhí)行的C語言簡歷源文件，感興趣的小伙伴們可以參考一下2016-07-07
迭代器的主要作用就是讓算法能夠不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu),其底層實(shí)際就是一個(gè)指針,或者是對(duì)指針進(jìn)行了封裝,迭代器失效,實(shí)際就是迭代器底層對(duì)應(yīng)指針?biāo)赶虻目臻g被銷毀了,對(duì)迭代器失效我們了解了,那么現(xiàn)在我們就分析,在vector中哪些操作會(huì)導(dǎo)致迭代器失效2023-08-08