c語言中的最大公約數

『壹』 c語言中求最大公約數的函數

#include
"stdio.h"
int
main()
{
int
d1,d2,r;
printf("輸入兩個正整數：");
scanf("%d
%d",&d1,&d2);
do
{
r=d1%d2;
d1=d2;d2=r;
}while(d2!=0);
printf("最大公約數是：%d",d1);
}
//遞歸法
#include
"stdio.h"
int
fun(int
d1,int
d2)
{
if(d2!=0)
return
fun(d2,d1%d2);
else
return
d1;
}
int
main()
{
int
d1,d2;
printf("輸入兩個正整數：");
scanf("%d
%d",&d1,&d2);
printf("最大公約數是：%d",fun(d1,d2));
}

『貳』 c語言編程-求最大公約數

求差判定法．

如果兩個數相差不大，可以用大數減去小數，所得的差與小數的最大公約數就是原來兩個數的最大公約數．例如：求78和60的最大公約數．78－60＝18，18和60的最大公約數是6，所以78和60的最大公約數是6．

如果兩個數相差較大，可以用大數減去小數的若干倍，一直減到差比小數小為止，差和小數的最大公約數就是原來兩數的最大公約數．例如：求92和16的最大公約數．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公約數是4，所以92和16的最大公約數就是4．

輾轉相除法．

當兩個數都較大時，採用輾轉相除法比較方便．其方法是：

以小數除大數，如果能整除，那麼小數就是所求的最大公約數．否則就用余數來除剛才的除數；再用這新除法的余數去除剛才的余數．依此類推，直到一個除法能夠整除，這時作為除數的數就是所求的最大公約數．

例如：求4453和5767的最大公約數時，可作如下除法．

5767÷4453＝1餘1314

4453÷1314＝3餘511

1314÷511＝2餘292

511÷292＝1餘219

292÷219＝1餘73

219÷73＝3

於是得知，5767和4453的最大公約數是73．

輾轉相除法適用比較廣，比短除法要好得多，它能保證求出任意兩個數的最大公約數．

--------------------------------------------------------------------------------

小學數學溫習過後，先來個兩個數遞歸版的

int GetGCDRec(int n, int m)
{
if (m < n)
{
m ^= n;
n ^= m;
m ^= n;
}

if (n == 0)
return m;
else
return GetGCDRec(n, m % n);
}
輾轉相除法，求一個數組中所有數的最大公約數

int GetGCD(int *arr, int len)
{
int iMax = arr[0], iCurr, iRemainder;

for(int i = 1; i < len; i++)
{
iCurr = arr[i];

if (iMax < iCurr)
{
iMax ^= iCurr;
iCurr ^= iMax;
iMax ^= iCurr;
}

iRemainder = iMax % iCurr;

while (iRemainder)
{
iMax = iCurr;
iCurr = iRemainder;
iRemainder = iMax % iCurr;
}

iMax = iCurr;
}//for

return iMax;

}
最小公倍數就是乘積除以最大公約數

int GetLCM(int *arr, int len)
{
int multiple = 1;

for (int i = 0; i < len; i++)
multiple *= arr[i];

return multiple / GetGCD(arr, len);
}

『叄』 C語言程序設計如何求最大公約數

求最大公約數演算法：

(1)輾轉相除法

兩整數a和b：

① a%b得余數c

② 若c=0，則b即為兩數的最大公約數，結束

③ 若c≠0，則a=b，b=c，再回去執行①

(2)相減法

兩整數a和b：

① 若a>b，則a=a-b

② 若a<b，則b=b-a

③ 若a=b，則a（或b）即為兩數的最大公約數，結束

④ 若a≠b，則再回去執行①

(3)窮舉法：

① i= a b中的小數

② 若a，b能同時被i整除，則i即為最大公約數，結束

③ i--，再回去執行②

相關代碼：

#include<stdio.h>
intxc_gcd(inta,intb)
{
	intc;
	c=a%b;
	while(c!=0)
	{
		a=b;
		b=c;
		c=a%b;
	}
	returnb;
}
intxj_gcd(inta,intb)
{
	while(a!=b)
	{
		if(a>b)
			a-=b;
		else
			b-=a;
	}
	returnb;
}
intqj_gcd(inta,intb)
{
	inti;
	i=(a>b)?a:b;
	while(a%i!=0&&b%i!=0)
		i--;
	returni;
}
voidmain()
{
	//inta=36,b=27;
	//inta=27,b=36;
	inta=100,b=201;
	printf("a=%db=%d
",a,b);
	printf("輾轉相除法求最大公約數=%d
",xc_gcd(a,b));
	printf("相減法求最大公約數=%d
",xc_gcd(a,b));
	printf("窮舉法求最大公約數=%d
",xc_gcd(a,b));
}

運行效果圖：