用三种算法求最大公约数

穷举法：将两个数a，b中较小的值赋给q，然后a除q，b也除q，若两者的余数同时为0

   时，那么q就是两者的最大公约数。若不等于0，则将q-1，然后继续a除q，b

   除q，直至余数同时为0。

#include <stdio.h>
void qongjufa()
{
 int a,b,c,q,m,n;
 printf("请输入所求的两个数\n");
 scanf("%d%d",&a,&b);
 m = a;
 n = b;
 if(a>b)//将较小的值赋给q
  q = b;
 else
  q = a;
 for(q;q>0;q--)
 {
  if(a%q == 0 && b%q == 0)//判断余数是否都为0
   break;//出循环
 }
 printf("最大公约数为%d\n",m,n,q);
 printf("\n");
}
int main()
{
 int q = 1;
 while(q)
 {
  qongjufa();
  return 0;
  printf("继续请按1，退出请按0\n");
  scanf("%d",&q);
 }
}
           

相除法:将两数ab相除，如余数c不等于0，就把b的值赋予a，c的值赋予b，直到c等于0，则最大公约数就是b

#include <stdio.h>
void xiangchu()
{
 int a = 0,b,c,m,n;
 printf("请输入所求的两个数字\n");
 scanf("%d%d",&a,&b);
 m = a;
 n = b;
 while(c)//判断c
 {
  c = a%b;
  if(c)//若c不等于0就把b的值赋予a，c的值赋予b
  {
   a = b;
   b = c;
  }
 }
 printf("%d和%d的最大公约数是:%d\n",m,n,b);//输出结果
 printf("\n");
}
int main()
{
 int i = 1;
 while(i)
 {
  xiangchu();
  printf("继续请按1，退出请按0。\n");
  scanf("%d",&i);
 }
 return 0;
}
           

将两数中大的a减去小的b,两数之值逐步减少,因而到有限步后必然获得相同的两数,也即所求的最大公约数

#include<iostream>
using namespace std;
int xiangjian(int a,int b)//相减法的具体步骤
{
 if(a==b) return a;//判断mn相等则已得出最大公约数
 if(a>b) return xiangjian(b,a-b);//如果不等则用大减小
 return xiangjian(a,b-a);
}
int main()
{
 int a,b;
 cout<<"请输入两个数："; 
 cin>>a>>b;
 printf("%d\n",xiangjian(a,b));
}