怎麼求最大公約數?

怎樣求.最大公約數？

1、寫出這幾個數的所有約數，然後選擇其中最大的一個；比如求6、8、10的最大公約數。6有約數1、2、3、6；8有1、2、4、8；10有1、2、5、10。公約數有1、2，其中最大的是2； 2、分解質因數法：還以6、8、10為例：6=2x3，8=2x2x2，10=2x5，其中共有的是2，所以它們的最大公約數是2（沒有時是1）； 3、最常用的是短除法：選擇它們共有的約數做除數，分別除以2以後還餘下3、4、5，只要有其中兩個數互質就算完成（這個不同於求最小公倍數，那是要除到任何兩個數都互質為止。

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

#include

int main()

{

int a,b,num1,num2,temp;

printf(&qu俯t;please input num1 and num2: ");

scanf("%d%d",&num1,&num2);

if(num1 >= num2)

{

a = num1;

b = num2;

}

if(num1 < num2)

{

a = num2;

b = num1;

}

while(b > 0)

{

temp = a % b;

a = b;

b = temp;

}

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

return 0;

}

求兩個自然數的最大公約數有哪些方法？

輾轉相除法:

大的數為a小的數為b

a除以b取餘c

a=b,b=c

重複上步直至b=0

最大公約數為a

更相減損術:

大的數為a小的數為b

c=a-b

若c>b

a=c

否則a=b

b=c

重複上步

直至b=c

此時b即為最大公約數

高2應該都會學到