欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++求最大公约数四种方法解析

程序员文章站 2022-03-14 17:44:38
c++求最大公约数的四种方法思路,供大家参考,具体内容如下将最近学的求最大公约数的四种方法总结如下:第一种:穷举法之一解释:拿其中一个数出来,用一个临时变量(tem)保存,每次都把那两个数除以这个临时...

c++求最大公约数的四种方法思路,供大家参考,具体内容如下

将最近学的求最大公约数的四种方法总结如下:

第一种:穷举法之一

解释:拿其中一个数出来,用一个临时变量(tem)保存,每次都把那两个数除以这个临时变量。如果能除断,直接返回tem;如果不能除断,tem- -,直到都能除断,再返回tem。tem就是它们的最大公约数。

#include <iostream>
using namespace std;
int commfactor1(int m, int n); //函数的声明
int main()
{
 int a, b;
 cin >> a >> b;
 cout << "这两个数的最大公约数为:" << commfactor1(a,b)<< endl;
 return 0;
}
int commfactor1(int m,int n)
{
 int tem;
 for (tem = m;; tem--)
 {
 if (m % tem == 0 && n % tem == 0)
 {
  break;
 }
 }
 return tem;
}

第二种:穷举法之二

解释:求出两数的所有公因子,再把公因子累乘得到最大公约数。

#include <iostream>
using namespace std;
int commfactor2(int m, int n); //函数的声明
int main()
{
  int a, b;
  cin >> a >> b;
  cout << "这两个数的最大公约数为:" << commfactor2(a,b)<< endl;
  return 0;
}
int commfactor2(int m,int n)
{
  int i;
  int factor = 1;
  for (i=2;i<=m&&i<<n;i++)
  {
    while(m % i == 0 && n % i == 0)  //这里不能用if语句,因为可能会有重复的公因子
    {
      factor = factor * i;
      m = m / i;
      n = n / i;
    }
  }
  return factor;
}

第三种:辗转相除法

解释:将两个数辗转相除直到余数为0。(具体思想请问度娘)

#include <iostream>
using namespace std;
int commfactor3(int m, int n); //函数的声明
int main()
{
 int a, b;
 cin >> a >> b;
 cout << "这两个数的最大公约数为:" << commfactor2(a,b)<< endl;
 return 0;
}
int commfactor3(int m,int n)
{
 int z = n;
 while (m % n != 0)
 {
 z = m % n;
 m = n;
 n = z;
 }
 return z;
}

第四种:辗转相减法

解释:将两个数辗转相减直到两数相等。(具体思想请问度娘)

#include <iostream>
using namespace std;
int commfactor4(int m, int n); //函数的声明
int main()
{
 int a, b;
 cin >> a >> b;
 cout << "这两个数的最大公约数为:" << commfactor4(a,b)<< endl;
 return 0;
}
int commfactor4(int m,int n)
{
 
 while (m != n)
 {
 if (m > n)
 {
 m = m - n;
 }
 else
 {
 n = n - m;
 }
 }
 return m;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

相关标签: C++ 最大公约数