用輾轉相除法求最大公約數c語言,c語言函數輾轉相除法求最大公約數

本文目錄一覽：

• 1、c語言輾轉相除法求最大公約數
• 2、c語言中，用輾轉相除法計算兩個數的最大公約數的具體方法是怎樣的？
• 3、如何用C語言求兩個數的最大公約數的三種演算法

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

可用遞歸來求。

推薦以下代碼：

#includestdio.h

int gcd(int a,int b) //求最大公約數函數

{

if (a%b==0) return b;

else return gcd(b,a%b); //輾轉相除法

}

void main()

{

int a,b;

scanf(“%d%d”,a,b);

printf(“%d\n”,gcd(a,b));

}

c語言中，用輾轉相除法計算兩個數的最大公約數的具體方法是怎樣的？

#include stdio.h

int gcd(int a, int b) {

int r;

do {

r = a % b;

a = b;

b = r;

} while (r);

return a;

}

int main(void) {

int a, b;

printf(“Input two integers: \n”);

scanf(“%d%d”, a, b);

printf(“The greatest common divisor is: %d\n”, gcd(a, b));

return 0;

}

原理：

輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的：

1. 若 r 是 a ÷ b 的餘數，則

gcd(a,b) = gcd(b,r)

2. a 和其倍數之最大公因子為 a。

另一種寫法是：

1. a ÷ b，令r為所得餘數（0≤rb）

若 r = 0，演算法結束；b 即為答案。

2. 互換：置 a←b，b←r，並返回第一步

如何用C語言求兩個數的最大公約數的三種演算法

1、相減法

#includelt;stdio.hgt;

int main()

{

int a,b;

int c=0;//計數器

while(1)//循環判斷的作用

{

printf(“輸入兩個數字求最大公約數:”);

scanf(“%d%d”,a,b);

while(a!=b)

{

if(agt;b)

a=a-b;

else

b=b-a;

c++;

}

printf(“最大公約數是:%d\n”,a);

printf(“%d\n”,c);

}

return 0;

}

運行效果：

2、輾轉相除法：

#includelt;stdio.hgt;

int a,b,temp;

int Division(){

printf(“請輸入兩個數(a,b)：\n”);

scanf(“%d,%d”,a,b);

if(alt;b){

temp=a;

a=b;

b=temp;

}

while(a%b!=0){

temp=a%b;

a=b;

b=temp;

}

printf(“最大公約數為：%d\n”,b);

return 0;

}

3、窮舉法

#includelt;stdio.hgt;

int main()

{

int a,b,c;

int d=0;//計數器

while(1)

{

printf(“輸入兩個數字求最大公約數:”);

scanf(“%d%d”,a,b);

c=(agt;b)?b:a;//三目運算符

while(a%c!=0||b%c!=0)

{

c–;

d++;

}

printf(“最大公約數是:%d\n”,c);

printf(“%d\n”,d);

}

return 0;

}