C語(yǔ)言最大公約數(shù)示例教程
窮舉法
（1） i=?a ，b中較小的數(shù)
（2）若a，b能同時(shí)被i整除，則i即為最大公約數(shù)，結(jié)束
（3）若不能，則 i--，再回去執(zhí)行（2）
#include<stdio.h>
int main()
{
int i = 0;
int j = 0;
scanf("%d %d", &i, &j);
int k = i > j ? i : j;//i>j,k=i;i<j,k=j
while(1)
{
if (i%k == 0 && j%k == 0)
{
printf("最大公約數(shù)為；%d\n", k);
break;
}
k--;
}
return 0;
}
?輾轉(zhuǎn)相除法
輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)的步驟如下：
（1）先用小的一個(gè)數(shù)除大的一個(gè)數(shù)，得第一個(gè)余數(shù)；
（2）再用第一個(gè)余數(shù)除小的一個(gè)數(shù)，得第二個(gè)余數(shù)；
（3）又用第二個(gè)余數(shù)除第一個(gè)余數(shù)，得第三個(gè)余數(shù)；
這樣逐次用后一個(gè)數(shù)去除前一個(gè)余數(shù)，直到余數(shù)是0為止。那么，最后一個(gè)除數(shù)就是所求的最大公約數(shù)。
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
int c = 0;
scanf("%d %d", &a, &b);
while (c = a%b)
{
a = b;
b = c;
}
printf("%d\n", b);
return 0;
}
?輾轉(zhuǎn)相減法
兩整數(shù)a和b：
（1） 若a>b，則a=a-b
（2）若a<b，則b=b-a
（3） 若a=b，則a（或b）即為兩數(shù)的最大公約數(shù)，結(jié)束
（4）若a≠b，則再回去執(zhí)行（1）
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d%d", &a, &b);
int ret = 0;
while (1)
{
if (a < b)
{
int tmp = 0;
tmp = a;
a = b;
b = tmp;
}
ret = a - b;
if (ret == b)//判斷
{
printf("ret = %d", ret);
break;
}
else//交換
{
a = b;
b = ret;
}
}
return 0;
}
以上就是C語(yǔ)言最大公約數(shù)示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言最大公約數(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++可變參數(shù)函數(shù)的實(shí)現(xiàn)方法示例
這篇文章主要給大家介紹了關(guān)于C++可變參數(shù)函數(shù)的實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容的string
最近工作中使用C語(yǔ)言，但又苦于沒(méi)有高效的字符串實(shí)現(xiàn)，字符串的拼接和裁剪都很麻煩，而且每個(gè)字符串都需要申請(qǐng)內(nèi)存，內(nèi)存的申請(qǐng)和釋放也很容易出bug，怎么高效的實(shí)現(xiàn)一個(gè)不需要處理內(nèi)存問(wèn)題并且可以動(dòng)態(tài)擴(kuò)容進(jìn)行拼接和裁剪的string呢？本文就來(lái)詳細(xì)講講2023-04-04
這篇文章主要介紹了VC多線程編程,實(shí)例形式詳細(xì)分析了多線程編程的原理與實(shí)現(xiàn)方法,具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-10-10
淺談2路插入排序算法及其簡(jiǎn)單實(shí)現(xiàn)
這篇文章主要介紹了淺談2路插入排序算法及其簡(jiǎn)單實(shí)現(xiàn),雖算不上是常用的排序方法,但在數(shù)據(jù)庫(kù)等方面依然有用上的機(jī)會(huì),需要的朋友可以參考下2015-08-08
這篇文章主要介紹了實(shí)現(xiàn)去除c語(yǔ)言注釋的小工具，說(shuō)是C語(yǔ)言，但其實(shí)所有C語(yǔ)系的都可以，比如Java,需要的朋友可以參考下2014-02-02
這篇文章主要介紹了如何在C++類的外部調(diào)用類的私有方法，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的朋友可以參考一下2022-09-09
Visual?Studio?2022?激活碼(親測(cè)可用)
在?Visual?Studio?2019?的基礎(chǔ)上，新版集成開(kāi)發(fā)壞境提供了非常多的改進(jìn)，包括對(duì)?64?位、.NET?6?的支持，為核心調(diào)試器提供更好的性能。本文給大家分享Visual?Studio?2022?激活碼，需要的朋友參考下吧2021-12-12
MD5（Message?Digest?Algorithm?5）是一種常用的哈希函數(shù)算法，這篇文章主要介紹了C語(yǔ)言如何獲取文件MD5值，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-08-08
C++設(shè)計(jì)模式中控制反轉(zhuǎn)與依賴注入淺析
這篇文章主要介紹了C++設(shè)計(jì)模式中控制反轉(zhuǎn)與依賴注入，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2023-01-01
C++實(shí)現(xiàn)LeetCode(154.尋找旋轉(zhuǎn)有序數(shù)組的最小值之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(154.尋找旋轉(zhuǎn)有序數(shù)組的最小值之二),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07