两个整数的最大公约数

两个整数的最大公约数（C语言程序设计现代方法第二版第六章6.2）
/*

1. 辗转相除法

辗转相除法

如果b等于0，计算结束，a就是最大公约数；
否则，计算a除以b的余数，让a等于b，而b等于那个余数；
回到第一步。
a	 b	  t
12	 18	  12
18	 12	  6
12	 6	  0
6	 0
*/
#include <stdio.h>
int main()
{
	int a,b,t;
	scanf("%d %d", &a,&b);
	while (b!=0){
		t=a % b;
		a=b;
		b=t;
	}
	printf("%d\n",a);
	return 0;
	
}
 

2. 枚举法

枚举法

#include <stdio.h>
int main()
{
	int a,b,min,i=1,gcd;
	scanf("%d / %d", &a, &b);
	if(a>b){
		min=a;
	}else{
		min=b;
	}
	while (i<min){
		if(a%i== 0){
			if(b%i== 0){
				gcd=i;
			}
		}i++;
	}//当然可以把while改写为for语句
	printf("gcd=%d\n",gcd);
	}

3. 递归

#include <stdio.h>
int hcf(int n1, int n2);
int main()
{
   int n1, n2;
   printf("输入两个正整数(n1 / n2): ");
   scanf("%d / %d", &n1, &n2);
 
   printf("%d 和 %d 的最大公约数为 %d", n1, n2, hcf(n1,n2));
   return 0;
}
 
int hcf(int n1, int n2)
{
    if (n2 != 0)
       return hcf(n2, n1%n2);
    else 
       return n1;
}

#include <stdio.h>

int main(void)
{
    int x, y, gcd;
    printf("请输入两个正整数(n1 / n2)：");
    scanf("%d / %d", &x, &y);
    if(x < y)
        gcd = x;
    else
        gcd = y;
    while(x % gcd ||y % gcd)
        gcd--;
    printf("gcd = %d\n", gcd);

    return 0;
}

5. 适用正数负数

适用正数负数

#include <stdio.h>
int main()
{
	int n1, n2;
	printf("输入两个数(n1 / n2)：");
	scanf("%d / %d", &n1,&n2); 
	
	n1 = ( n1 > 0) ? n1 : -n1;
	n2 = ( n2 > 0) ? n2 : -n2;
	
	while(n1 != n2){
		if(n1 > n2){
			n1 -=n2;
		}else{
			n2 -=n1;
		}
	}
	
	printf("GCD=%d\n", n1);
	
	return 0;
}

6.
/使用 for 和 if/

#include <stdio.h>
int main()
{
	int n1,n2,i,gcd;
	
	printf("输入两个正整数 (n1 / n2)：");
	scanf("%d / %d", &n1,&n2);
	
	for(i=1;i<=n1 && i<=n2;i++){
		if(n1%i==0 && n2%i==0){
			gcd=i;
		}
		
	}
	
	printf("%d 和 %d的最大公约数是 %d", n1, n2,gcd);
	return 0;
 } 

7.
/使用 while 和 if/

#include <stdio.h>
int main()
{
	int n1,n2;
	
	printf("输入两个数(n1 / n2)：");
	scanf("%d / %d", &n1, &n2);
	
	while(n1!=n2){
		if (n1>n2){
			n1 -=n2;
		}else{
			n2 -=n1;
		}
	}
	
	pritnf("GCD=%d\n",n1);
	return 0;
}