用C++求最大公约数

香蕉那个不拿拿

用计算机傻算公约数
先穷举所有因数
再一一配对。

1. #include<iostream>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.         int max = 0;
   
6.         long long a [5000];
   
7.         long long b [5000];
   
8.         int anumber,bnumber;
   
9.         cin>>anumber>>bnumber;
   
10.         int counta = 0,countb = 0;
    
11.         for (int i = 1;i <= anumber / 2;i++)
    
12.         {
    
13.                 if (anumber % i  == 0)
    
14.                 {
    
15.                         counta+=1;
    
16.                         a [counta] = i;
    
17.                         a [counta + 1] = anumber/ i;
    
18.                         counta+=1;
    
19.                 }
    
20.         }
    
21.         for (int i = 1;i <= bnumber / 2;i++)
    
22.         {
    
23.                 if (bnumber % i  == 0)
    
24.                 {
    
25.                         countb += 1;
    
26.                         b [countb] = i;
    
27.                         b [countb + 1] = bnumber/ i;
    
28.                         countb += 1;
    
29.                 }
    
30.         }
    
31.         for (int i = 1;i <= counta;i++)
    
32.         {
    
33.                 for (int j = 1;j <= countb;j++)
    
34.                 {
    
35.                         if (a[i] == b[j])
    
36.                         {
    
37.                                 if (a[i] > max)
    
38.                                 {
    
39.                                         max = a[i];
    
40.                                 }
    
41.                         }
    
42.                 }
    
43.         }
    
44.         cout<<max;
    
45. }

复制代码

zhangjinxuan

欧几里得算法。

原理如下：

gcd(x, y) = gcd(y, x % y) (y != 0)
gcd(x, 0) = x

因此，我们可以写出如下的求最大公因数代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. template<typename T>
   
5. T gcd(T x, T y) {
   
6.         return y ? gcd(y, x % y) : x;
   
7. }
   
8. 
   
9. int main() {
   
10.         long long a, b;
    
11.         printf("Enter two 64 bit numbers: ");
    
12.         scanf("%lld%lld", &a, &b);
    
13.         printf("gcd(%lld, %lld) = %lld\n", a, b, gcd(a, b));
    
14.     return 0;
    
15. }

复制代码

香蕉那个不拿拿

zhangjinxuan 发表于 2023-7-16 20:11
欧几里得算法。

原理如下：

是
有一个辗转相除法
更简单