c++求最大公约数比较
时间: 2023-11-03 12:40:06 浏览: 64
求最大公约数的方法有很多种,例如辗转相除法、质因数分解法、更相减损术等。不同的方法在不同的情况下可能有不同的优劣性。
辗转相除法是一种简单易行的方法,但当两个数较大时,计算量会比较大,效率较低。质因数分解法可以在一定程度上减少计算量,但需要将两个数都分解质因数,若两个数中有一个数的质因数较多,则计算量仍然很大。更相减损术在计算过程中可能会出现较大的差值,需要多次计算,效率也较低。
因此,在实际应用中,应根据具体的情况选择合适的方法,以达到较优的效果。同时,也可以使用现代计算机快速计算最大公约数,以提高计算效率。
相关问题
C++ 求最大公约数
根据提供的引用内容来看,有三种方法可以求解最大公约数。
方法一,通过辗转相除法来求解最大公约数。这种方法的实现代码如下:
```cpp
#include<iostream>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
int a=1; //默认在最大公约数为1
int times = 0;
if(n%m==0||m%n==0) //若nm直接能整除,则最大公约数即是较小那个的数
{
times++;
m = m < n ? m : n;
}
while((a=n%m)!=0)
{
times++;
n=m;
m=a;
}
cout<<"循环次数为:"<<times<<endl;
cout<<"最大公约数为:"<<m<<endl;
return 0;
}
```
方法二,通过从较小数开始依次找到能同时被两个数整除的第一个整数来求解最大公约数。这种方法的实现代码如下:
```cpp
#include<iostream>
using namespace std;
int main() {
int n,m;
int times = 0;
cin>>n>>m; //输入两个数
int x = n<m?n:m; //m,n的最大的公约数永远不可能是较大的那个数,只可能是较小的数
for(x;x>=1;x--) {
times++;
if(n%x==0&&m%x==0) //x正好被n,m整除,则找到了x
break;
}
cout<<"循环次数为:"<<times<<endl;
cout<<"最大公约数为:"<<x<<endl;
return 0;
}
```
方法三,通过差和减数相等的方式求解最大公约数,公式为:最大公约数=相等的数*(2^除以二的次数)。这种方法的实现代码如下:
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int a, b, num=0,t;
cin >> a >> b;
if (a == b){
cout << a << endl;
return 0;
}
t=a,a = max(a, b), b = min(t, b);
while ((a % 2 == 0) && (b % 2 == 0)){
a /= 2, b /= 2, num++;
}
while (b != a - b){
t=a-b,a = max(b, t), b = min(b, t);
}
cout << b * (1<<num) << endl;
return 0;
}
```
以上是求解最大公约数的三种方法和对应的实现代码。通过选择其中一种方法,根据输入的两个数的不同情况,可以得到最大公约数。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [【C++】求两个数的最大公约数——方法大全](https://blog.csdn.net/ly_6699/article/details/90719315)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *3* [C++之 最大公约数求法](https://blog.csdn.net/lxiisbshcuia/article/details/124401871)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]
c++求最大公约数代码
以下是C++求最大公约数的代码:
```c++
#include<iostream>
using namespace std;
int gcd(int x, int y) {
int i;
for(i = 1000; i > 0; i--) {
if((x % i == 0) && (y % i == 0)) {
return i;
}
}
}
int main() {
int a, b, res;
cin >> a >> b;
res = gcd(a, b);
cout << res << endl;
return 0;
}
```
该代码使用了暴力遍历的方法,从1000开始递减遍历,找到a和b的最大公约数后返回。