最大公約數相除法c語言

❶ c語言求最大公約數的代碼

你的代碼，主要的錯誤在for循環里的判斷條件，應該是a%i!=0&&b%i!=0
不等號；但是，是了很久，發現這樣的演算法或者說思路也是錯誤的！因為你這樣找到的只是兩個數的最小公約數，而非最大公約數的，你可以用原來的想法，i
從
兩個數中較小者那個從大到小去循環，從而找到兩個數的公約數，也就是(從大到小)倒這來找公約數；或者建議你考慮輾轉相除法，輾轉相除法的思路是這樣的：若
m和n為這連個正整數，有：當m>n,m與n
的最大公約數等於
n
與
m%n的最大公約數當n=0
,m與
n
的最大公約數等於
m,以下是演算法，使用for語句：#include<stdio.h>
#include<windows.h>
int
main(){
int
a,b,m,n,r;
printf("輸入兩個正整數(請用逗號隔開):");
scanf("%d%d",&a,&b);
if(a>b)
{
m=a;
n=b;
}
else
{
m=b;
n=a;
}
for(r=b;r!=0;){
r=m%n;
m=n;
n=r;
}
printf("%d
和
%d
的最大公約數是:%d\n",a,b,m);
system("PAUSE");
return
0;
}

❷ c語言輾轉相除法求最大公約數

可用遞歸來求。

推薦以下代碼：

#include<stdio.h>
intgcd(inta,intb)//求最大公約數函數
{
	if(a%b==0)returnb;
	elsereturngcd(b,a%b);//輾轉相除法
}
voidmain()
{
	inta,b;
	scanf("%d%d",&a,&b);
	printf("%d
",gcd(a,b));
}

❸ 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語言

int euclid(int m,int n)
{
int r;
r=m%n;
while(r)
{
m=n;
n=r;
r=m%n;
}
return n;
}
//這個你可以參考一下，希望能採納

❺ C語言 求最大公約數 輾轉相除法的問題

r==x%y; //這只是個邏輯比較，沒有給r賦值
改成
r = x%y; //這才是給r賦值