C語言最大公約數示例教程
窮舉法
（1） i= a ，b中較小的數
（2）若a，b能同時被i整除，則i即為最大公約數，結束
（3）若不能，則 i–，再回去執行（2）
#include<stdio.h>
int main()
{
int i = 0;
int j = 0;
scanf("%d %d", &i, &j);
int k = i > j ? i : j;//i>j,k=i;i<j,k=j
while(1)
{
if (i%k == 0 && j%k == 0)
{
printf("最大公約數為；%d\n", k);
break;
}
k--;
}
return 0;
}
輾轉相除法
輾轉相除法求兩個數的最大公約數的步驟如下：
（1）先用小的一個數除大的一個數，得第一個餘數；
（2）再用第一個餘數除小的一個數，得第二個餘數；
（3）又用第二個餘數除第一個餘數，得第三個餘數；
這樣逐次用後一個數去除前一個餘數，直到餘數是0為止。那麼，最後一個除數就是所求的最大公約數。
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
int c = 0;
scanf("%d %d", &a, &b);
while (c = a%b)
{
a = b;
b = c;
}
printf("%d\n", b);
return 0;
}
輾轉相減法
兩整數a和b：
（1） 若a>b，則a=a-b
（2）若a<b，則b=b-a
（3） 若a=b，則a（或b）即為兩數的最大公約數，結束
（4）若a≠b，則再回去執行（1）
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d%d", &a, &b);
int ret = 0;
while (1)
{
if (a < b)
{
int tmp = 0;
tmp = a;
a = b;
b = tmp;
}
ret = a - b;
if (ret == b)//判斷
{
printf("ret = %d", ret);
break;
}
else//交換
{
a = b;
b = ret;
}
}
return 0;
}
以上就是C語言最大公約數示例詳解的詳細內容，更多關於C語言最大公約數的資料請關註WalkonNet其它相關文章！