C语言使用素因子法求最大公约数

C语言中可以使用素因子分解的方法，也称为质因数分解法，来求两个整数的最大公约数（Greatest Common Divisor, GCD）。这种算法的基本思想是将每个数分解成素因数乘积的形式，然后找出它们公共的素因数部分，即最大公约数。

以下是基本步骤：
1. **分解**：分别对给定的两个数n1和n2进行质因数分解，直到不能再继续分解为止，得到各自的素因子集合A和B。
2. **比较**：从最小的素数开始，检查这两个素数是否同时出现在A和B中，如果都存在，则该素数就是最大公约数的一部分，并将其从两个集合中移除；如果只在一个集合中出现，那么另一个集合不需要再考虑这个素数。
3. **递归**：重复此过程，直到其中一个集合为空或者只剩下一个公共素因数，此时该素因数即为最大公约数。

以下是简单的C语言代码示例：

#include <stdio.h>

// 判断一个数是否为素数
int is_prime(int num) {
    if (num <= 1) return 0;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

// 获取素因子分解
void prime_factors(int num, int factors[]) {
    for (int i = 2; ; i++) {
        while (num % i == 0 && is_prime(i)) {
            factors[num / i]++;
            num /= i;
        }
        if (num == 1) break;
    }
}

// 求最大公约数
int gcd(int n1, int n2) {
    int factors1[100], factors2[100];
    prime_factors(n1, factors1);
    prime_factors(n2, factors2);

    // 比较并累计共同的素因子
    int gcd_value = 1;
    for (int i = 2; i < factors1[1] + 1 || i < factors2[1]; i++) {
        while (factors1[i] > 0 && factors2[i] > 0) {
            gcd_value *= i;
            factors1[i]--;
            factors2[i]--;
        }
    }

    return gcd_value;
}

int main() {
    int n1, n2;
    printf("Enter two numbers: ");
    scanf("%d %d", &n1, &n2);
    printf("The GCD of %d and %d is %d\n", n1, n2, gcd(n1, n2));
    return 0;
}