本文目錄一覽：
c語言求兩個數的最大公約數
思路：求兩個數的最大公約數使用輾轉相除法。
輾轉相除法，
又名歐幾里德算法（Euclidean
algorithm）乃求兩個正整數之最大公因子的算法。原理：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數。
參考代碼：
#include stdio.h
int main()
{
int x,y,z;
scanf(“%d%d”,x,y);
while(x!=0)
{
z=x%y;
x=y;
y=z;
}
printf(“%d\n”,z);
return 0;
}
/*
運行結果：
6 27
3
*/
C語言程序設計如何求最大公約數
最大公約數算法：
(1)輾轉相除法
兩整數a和b：
① a%b得餘數c
② 若c=0，則b即為兩數的最大公約數，結束
③ 若c≠0，則a=b，b=c，再回去執行①
(2)相減法
兩整數a和b：
① 若ab，則a=a-b
② 若ab，則b=b-a
③ 若a=b，則a（或b）即為兩數的最大公約數，結束
④ 若a≠b，則再回去執行①
(3)窮舉法：
① i= a b中的小數
② 若a，b能同時被i整除，則i即為最大公約數，結束
③ i–，再回去執行②
c語言最大公約數的求法
最大公約數c語言編程的常用思路是：按照從大（兩個整數中較小的數）到小（到最小的整數1）的順序求出第一個能同時整除兩個整數的自然數，即為所求。
兩個數的最大公約數有可能是其中的小數，所以在按從大到小順序找尋最大公約數時，循環變量i的初值從小數n開始依次遞減，去尋找第一個能同時整除兩整數的自然數，並將其輸出。
需要注意的是，雖然判定條件是i0，但在找到第一個滿足條件的i值後，循環沒必要繼續下去，如，25和15，最大公約數是5，對於後面的4、3、2、1沒必要再去執行，但此時判定條件仍然成立，要結束循環只能藉助break語句。
具體代碼實現：
#includestdio.h
int main()
{
int m,n,temp,i;
printf(“Input mn:”);
scanf(“%d%d”,m,n);
if(mn)/*比較大小，使得m中存儲大數，n中存儲小數*/
{/*交換m和n的值*/
temp=m;
m=n;
n=temp;
}
for(i=n;i0;i–)/*按照從大到小的順序尋找滿足條件的自然數*/
if(m%i==0n%i==0)
{/*輸出滿足條件的自然數並結束循環*/
printf(“The GCD of%d and%d is:%d\n”,m,n,i);
break;
}
return 0;
}
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/258548.html
微信掃一掃 
支付寶掃一掃 