辗转相除法求最大公因数-C语言_辗转相除法求最大公因式c语言

  辗转相除法，又名欧几里德算法，是求最大公约数的一种方法。以除数和余数反复做除法运算，最终当余数为0时，取当前算式除数为最大公约数。

例1：求2015和15的最大公因数。
2015 = 15 * 134 + 5
15 = 5 * 3 + 0
因此，最大公因数为：5，即：(2015,15)=5。

例2：求1987和654的最大公因数。
1987 = 654 * 3 + 25
654 = 25 * 26 + 4
25 = 4 * 6 + 1
4 = 1 * 4 + 0
因此，最大公因数为：1，即：(1987,654)=1，则1987与654互素。

#include <stdio.h>
#include <stdlib.h>
int home()
{
    int X, Y, Z,r;//第一个数，第二个数，商，余数 
    printf("请依次输入两个正整数:");
    scanf("%d %d", &X, &Y);
    if (X < Y)//先调整大小，使X为两数中较大者，Y为较小者
    {
        int t = X;
        X = Y;
        Y = t;
    }
    r = X % Y;//求得余数
    //while(r != 0)
    while(1)
    {
    	//printf("%d\n",r);
    	Z = X / Y;//商 
    	printf("%d = %d  * %d + %d\n",X,Y,Z,r);
    	if (r == 0)
    		break;
        X = Y;   
        Y = r;           //不断调整相除的值
        r = X % Y;
        if(r == 0)
        {
        	Z = X / Y;//商 
        	printf("%d = %d  * %d + %d\n",X,Y,Z,r);
			break;
		} 
    }//当r不为0，退出循环，得到Y为最大公约数
    printf("最大公因数为：%d\n", Y);//打印最大公约数
}

int main()
{
	while(1)
	{
		home();
	}
	system("pause");
	return 0;
}

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

例3：设a= 46480, b = 39423,求整数s，t ,使得sa＋tb = (a, b)。

则有

因此，整数s =-22703，t =26767满足sa + tb=(a,b)。