求两个数的最大公约数的三种算法

107 阅读 0 评论 71 点赞

我是靠谱客的博主顺心天空，最近开发中收集的这篇文章主要介绍求两个数的最大公约数的三种算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

从键盘输入两个整数，求着两个整数的最大公约数。

解题思路：

从键盘输入两个数，通过以下的三个方法实现求两个数的最大公约数：

辗转相除法：取两个数中最大的数做除数，较小的数做被除数，用最大的数除较小数，如果余数为0，则较小数为这两个数的最大公约数，如果余数不为0，用较小数除上一步计算出的余数，直到余数为0，则这两个数的最大公约数为上一步的余数。

相减法：取两个数中的最大的数做减数，较小的数做被减数，用最大的数减去小数，如果结果为0，则被减数就是这两个数的最大公约数，如果结果不为0，则继续用这两个数中最大的数减较小的数，直到结果为0，则最大公约数为被减数。

穷举法：将两个数作比较，取较小的数，以这个数为被除数分别和输入的两个数做除法运算，被除数每做一次除法运算，值减少1，直到两个运算的余数都为0，则该被除数为这两个数的最大公约数。

/**
* Author:Probie
* Date:2017-3-21 21:38:14
*/

#include <stdio.h>
int a, b, temp;
//辗转相除法实现
int Division(){
   printf("请输入两个数(a,b)：n");
   scanf("%d,%d",&a,&b);
   if(a < b){
       temp = a;
       a = b;
       b = temp;

   }
   while(a%b != 0){
           temp = a%b;
           a = b;
           b = temp;
   }
   printf("最大公约数为：%dn",b);
   return 0;
}
//相减法实现
int Subtract(){
   printf("请输入两个数(a,b)：n");
   scanf("%d,%d",&a,&b);
   if(a < b){
       temp = a;
       a = b;
       b = temp;
   }
   while(a-b != 0){
           temp = a-b;
           a = b;
           b = temp;
   }
   printf("最大公约数为：%dn",b);
   return 0;
}
//穷举法实现
int Exhaus() {
   printf("请输入两个数(a,b)：n");
   scanf("%d,%d",&a,&b);
   if(a < b) {
       temp = a;
       a = b;
       b = temp;
   }
   for(temp = b; a%temp || b%temp; temp--);
   printf("最大公约数为：%dn",temp);
   return 0;
}

int main(){
   int nub;
   printf("n求两个数的最大公约数:");
   printf("n1、辗转相除法");
   printf("n2、相减法");
   printf("n3、穷举法");
   printf("n请选择你要使用的方法：n");
   scanf("%d",&nub);
   switch(nub){
       case 1:
           Division();
           break;
       case 2:
           Subtract();
           break;
       case 3:
           Exhaus();
           break;
   }
   return 0;
}