求最大公约数的三种方法

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>
#include <stdlib.h>
int main()
{
// 1.穷举法：将两个数中较小的数做为被除数，，与输入的两个数相除取余，每除一次这个数 减1，               直到两个除式取余同时为0
	int i;  //被除数
	int a =0;
	int b =0;
	int temp;
	scanf("%d,%d",&a,&b);
	printf("%d,%d\n", a, b);
	if (a > b)
	{
		i = b;
	}
	else
	{
		i = a;
	}
	for (i; i > 0; i--)
	{
		if (0 == a%i && 0 == b%i)
		{
			printf("%d\n", i);
		}
	}
	printf("%d\n", b);
	system("pause");
	return 0;
}

2.辗转相减法

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
#include <stdio.h>
#include <stdlib.h>
int main()
{
	int a =0;
	int b =0;
	int temp;
	scanf("%d,%d",&a,&b);
	printf("%d,%d\n", a, b);
    flag:
		if (a < b)
		{
			temp = a;
			a = b;
			b = temp;
		}
		if (a - b != 0)//80-50 b50 a50 b35  a35 b15  20 15  15 5  10 5   5
		{
			a = a - b;  //     a35   a15     20         5         10     5
			goto  flag;
		}
    
    
    printf("%d\n", b);
	system("pause");
	return 0;
}

3.辗转相除法

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
#include <stdio.h>
#include <stdlib.h>
int main()
{
	int a =0;
	int b =0;
	int temp;
	scanf("%d,%d",&a,&b);
	printf("%d,%d\n", a, b);

//3.相除法： 例如：80 50 ：80%50 = 30； 50 % 30 =20；20%10 =10；
	if (a < b)
	{
		temp = a;
		a = b;
		b = temp;
	}
	while (0 != a%b)
	{
		temp = a%b;
		a = b;
		b = temp;
		printf("a=%d  b=%d\n", a, b);//查看步骤
	}
	printf("%d\n", b);
	system("pause");
	return 0;
}