求最大公约数的三种算法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std; 
  
int gcdByBruteForce(int a, int b) {  
    for (int i = min(a, b); i > 0; --i) {  
        if (a % i == 0 && b % i == 0) {  
            return i;  
        }  
    }  
    return 1; 
}  

int gcdByEuclidean(int a, int b) {  
    while (b != 0) {  
        int temp = b;  
        b = a % b;  
        a = temp;  
    }  
    return a;  
}

void prime_factors(int n,vector<int>& factors) {
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
}

int gcd(int a, int b) {
    vector<int> factors_a, factors_b;
    prime_factors(a, factors_a);
    prime_factors(b, factors_b);

    for (int factor : factors_a) {
        if (find(factors_b.begin(), factors_b.end(), factor) != factors_b.end()) {
            return factor;
        }
    }
    return 1;
}

int main(){
	int m,n;  
   	cin>>m>>n;
   	cout<<gcdByBruteForce(m,n)<<"\n";
   	cout<<gcdByEuclidean(m,n)<<"\n";
   	cout<<gcd(m,n)<<"\n";
    return 0;   
}

1. gcdByBruteForce(int a, int b)：这个函数通过暴力枚举的方式寻找两个数的最大公约数。最坏情况下，时间复杂度为O(min(a, b))，因为需要遍历从1到min(a, b)的所有整数，检查它们是否同时是a和b的因子。

2. gcdByEuclidean(int a, int b)：这个函数使用辗转相除法（欧几里得算法）来计算最大公约数。在最坏情况下，时间复杂度为O(log(min(a, b)))，因为每次迭代都会将其中一个数减小至少一半，直到其中一个数变为0。

3. gcd(int a, int b)：这个函数首先计算两个数的质因数分解，然后找出它们的公共质因数作为最大公约数。质因数分解的时间复杂度取决于输入数字的大小，但对于较小的数字，通常可以在O(sqrt(n))的时间内完成。在最坏情况下，如果两个数都有大量的质因数，那么时间复杂度可能接近O(n)，其中n是输入数字的大小。然而，对于大多数实际应用，我们可以认为质因数的数量是有限的，因此这个函数的时间复杂度可以近似为O(sqrt(a) + sqrt(b))。