C++求公约数 |21xrx.com

C++求公约数

2023-07-14 16:35:06 深夜i -- --

C++ 求公约数

在数学中，公约数是指同时被两个或多个整数除尽的正整数，也就是可以同时整除两个或多个数的最大正整数。而在编程中，求最大公约数是一个常见的问题，本文将介绍使用C++编写求公约数的方法。

一、暴力枚举法

最简单粗暴的方法就是暴力枚举法，遍历两个数的所有可能的约数，找到最大的公约数。代码如下：


#include<iostream>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  int gcd = 1;
  for(int i=1;i<=min(a,b);i++){
    if(a%i==0 && b%i==0)
      gcd = i;
    
  }
  cout << gcd << endl;
  return 0;
}

二、辗转相减法

辗转相减法又称为欧几里得算法，其基本思想是通过两个数相减，不断更新两个数的值，直到两数相等，这个相等的数就是最大公约数。代码如下：


#include<iostream>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  while(a!=b){
    if(a>b)
      a-=b;
    
    else
      b-=a;
    
  }
  cout << a << endl;
  return 0;
}

三、辗转相除法

辗转相除法也称为欧几里得算法，与辗转相减法类似，但是更快速，其基本思想是通过两个数取模计算，不断更新两个数的值，直到其中一个数变为0，另一个数就是最大公约数。代码如下：


#include<iostream>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  int gcd;
  while(b)
    int r = a%b;
    a=b;
    b=r;
  
  gcd = a;
  cout << gcd << endl;
  return 0;
}

以上三种方法都可以用来求最大公约数，使用时可以根据实际情况选择。需要注意的是，辗转相减法在两个数差异较大时会执行缓慢，辗转相除法则无此问题，但需要注意较大的整数相除可能会造成上溢或下溢的问题，应注意溢出问题的处理。

上一篇: idea打包java可执行jar包

下一篇: C++基础题目总结

评论区

()

相似文章