C语言实现：最大公因数、最小公倍数及因式分解算法

本文主要介绍了C语言实现的经典算法，包括最大公因数（Greatest Common Divisor, GCD）、最小公倍数（Least Common Multiple, LCM）的计算以及整数的因式分解。 在计算最大公因数时，通常采用欧几里得算法（辗转相除法）。此算法的基本思想是：对于两个正整数m和n，如果n不等于0，则将m除以n得到余数r，然后用n替换m，用r替换n，重复此过程直到n等于0。此时，m就是最大公因数。在提供的代码中，通过一个while循环实现了这一算法： ```c int m, n, r; int s; printf("请输入两个整数："); scanf("%d%d", &m, &n); s = m * n; // 保存两数乘积 while (n != 0) { r = m % n; m = n; n = r; } printf("GCD: %d\n", m); ``` 最小公倍数可以通过最大公因数来求解，利用公式：GCD * LCM = 两数乘积。在找到GCD后，可以轻松地计算出LCM： ```c printf("LCM: %d\n", s / m); ``` 对于因式分解，代码中使用了一个简单的遍历法。输入一个整数n，从2开始尝试将其除尽，每次除以能整除n的数，直到n变成1。每找到一个因子，就打印出来并更新n的值： ```c int i, n; printf("请输入一个整数进行因式分解："); scanf("%d", &n); printf("%d=", n); for (i = 2; i * i <= n; ) { if (n % i == 0) { printf("%d*", i); n /= i; } else i++; } printf("%d\n", n); ``` 此外，还展示了如何生成一个素数表，用于快速查找和因式分解。`prime`函数生成小于或等于N的所有素数，并存储到数组`pNum`中；`factor`函数利用这个素数表对给定的数进行因式分解： ```c #define N 1000 int prime(int* pNum) { // ... 素数表生成逻辑 ... } void factor(int* table, int num) { // ... 因式分解逻辑 ... } ``` 这些算法在C语言中的实现，可以帮助理解和处理基础的数学问题，对于编程学习者来说是很好的实践练习。