C语言——最大公约数与最小公倍数的秘密
part1.求两个正整数的最大公约数之辗转相除
辗转相除,也叫欧几里得算法或除法求余法,是数学上用于计算两个正整数最大公约数(Greatest Common Divisor, GCD)的一种古老而有效的方法。它的基本原理是利用辗转相除法的性质:两个正整数a和b(假设a>b),它们的最大公约数等于b和a除以b的余数c的最大公约数。如果余数为0,则b就是原两数的最大公约数;若不为0,则继续将原来较小的数b作为新的被除数,原来的余数c作为新的除数,这个过程不断重复,直到余数为0为止。这种方法体现了递归的思想。实际代码如下:
#include<stdio.h> int main() { long a = 0; long b = 0; scanf("%ld %ld", &a, &b); long i = a; long j = b; long r = 0; while (r = i % j) { i = j; j = r; }//辗转相除法 //用较大数除以较小数,再用出现的余数去除除数,再用新出现的余数去除前面的余数, // 反复直到最后余数是0才终止循环,且最后的除数就是这两个数的最大公约数 printf("%ld\n", j); return 0; }
part2.求两个正整数的最小公倍数与最大公约数之和
欧几里得发现的定理(a,b)*[a,b]=a*b,其中最大公约数表示为:(a,b),最小公倍数表示为:[a,b]。
依此,我们不仅可以求最小公倍数,还可以求两个正整数的最小公倍数与最大公约数之和。
#include<stdio.h> int main() { long a = 0; long b = 0; scanf("%ld %ld", &a, &b); long i = a; long j = b; long r = 0; while (r = i % j) { i = j; j = r; } printf("%ld\n", a * b / j + j);//求两个正整数的最小公倍数与最大公约数之和 //i = a * b / j//这个是求两个正整数的最小公倍数 return 0; }
part3.求最小公倍数的另一种方法
优点:代码简洁;不足:运行时间比前面代码长
#include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); int i = 1; while ((a * i) % b) { i++; } printf("%d\n", a * i); return 0; }
代码解读:a*i是a的i倍,当a*i%b==0时,a*i也是b的k倍。依此方法可以试出a和b的最小公倍数。
注:本文并非完全原创,借鉴了很多大佬的思维与方法,望周知