编程求取两个整数的最大公约数.欧几里德算法

た入场券 2022-08-27 15:52 156阅读 0赞

/*
    编程求取两个整数的最大公约数。
    Enter two integers: 12 28
    Greatest common divisor: 4
    提示：分别用两个变量m、n存储两个整数。如果n为0，那么停止操作，
    m中的值就是最大公约数，否则计算m除以n的余数，把n保存到m中，并
    把余数保存到n中。然后重复上述过程，每次都先判定n是否为0。
    */
    
    #include <stdio.h>
    
    int main(void)
    {
    	int a, b, i, t;
    	scanf("%d%d", &a, &b);
    	if(a > b){
    		t = a;
    		a = b;
    		b = t;
    	}//确保ａ是最小值
    	for(i = a; i >= 2; i--){
    		if(a%i == 0 && b%i == 0){
    			printf("最大公约是:%d\n", i);
    			break;
    		}
    	
    	}
    
    	if(i == 1){
    		printf("两数只能同时被1整除\n");
    	}
    	return 0;
    }
    
    /*
    16 32
    最大公约是:16
    akaedu@akaedu-G41MT-D3:~/lin/715_hanshu$ ./zdgys 
    56 99
    两数只能同时被1整除
    akaedu@akaedu-G41MT-D3:~/lin/715_hanshu$ ./zdgys 
    25 85
    最大公约是:5
    
    */<pre name="code" class="cpp">
    
    //欧几里德算法
    
    #include <stdio.h>
    
    int gcd(int a, int b)
    {
    	if(b == 0)
    		return a;
    	return gcd(b, a%b);
    }
    
    
    int main(void)
    {
    	int a, b;
    	printf("enter two number:\n");
    	scanf("%d%d", &a, &b);
    	printf("最大公约数为:%d\n", gcd(a, b));
    
    	return 0;
    }
    
    /*
    enter two number:
    16 8
    最大公约数为:8
    */

http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html