窮舉法
（1） i= a ，b中較小的數(shù)
（2）若a，b能同時(shí)被i整除，則i即為最大公約數(shù)，結(jié)束
（3）若不能，則 i--，再回去執(zhí)行（2）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#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("最大公約數(shù)為；%d\n", k); break; } k--; } return 0;} |
輾轉(zhuǎn)相除法
輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)的步驟如下：
（1）先用小的一個(gè)數(shù)除大的一個(gè)數(shù)，得第一個(gè)余數(shù)；
（2）再用第一個(gè)余數(shù)除小的一個(gè)數(shù)，得第二個(gè)余數(shù)；
（3）又用第二個(gè)余數(shù)除第一個(gè)余數(shù)，得第三個(gè)余數(shù)；
這樣逐次用后一個(gè)數(shù)去除前一個(gè)余數(shù)，直到余數(shù)是0為止。那么，最后一個(gè)除數(shù)就是所求的最大公約數(shù)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#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;} |
輾轉(zhuǎn)相減法
兩整數(shù)a和b：
（1） 若a>b，則a=a-b
（2）若a<b，則b=b-a
（3） 若a=b，則a（或b）即為兩數(shù)的最大公約數(shù)，結(jié)束
（4）若a≠b，則再回去執(zhí)行（1）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#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語(yǔ)言最大公約數(shù)示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言最大公約數(shù)的資料請(qǐng)關(guān)注服務(wù)器之家其它相關(guān)文章！
原文鏈接：https://blog.csdn.net/weixin_54342360/article/details/120789366
