算法 | 求最大公约数和最小公倍数

小学数学就学习了如何计算最大公约数(Greatest Common Factor,GCF)和最小公倍数(Lowest Common Multiple,LCM)。例如15和25的最大公约数是5，最小公倍数是75，数学老师会不厌其烦的用质数分解的方法讲解。那么，能不能用计算机来算？古希腊数学家欧几里得提出了最大公约数GCF的算法：

给出两个整数A和B

if B==0

则答案是A

else

答案是GCF(B,A%B)

这里%是取余运算，A%B的意思是A除以B，返回余数。例如5%2返回1，4%2返回0，即4能被2整除。

以上算法的大致思路是：如果B不等于0，则转为求B和A%B的最大公约数，并通过递归调用。来看一个例子

求35和25的最大公约数，过程如下表

有了求GCF的算法，求LCM就很简单了。求LCM关键是找到最大公约数GCF，算法如下

n=GCF(A,B)

LCM(A,B)=n*(A/n)*(B/n)

或者LCM(A,B)=A / n * B

用Fortran来实现

欧几里得的《几何原本》(Elements)是西方文明史上最有名气的著作之一，古往今来都作为标准教科书使用，书中展现了他大师级的逻辑推理。事实上，“证明题”就源自他的《几何原本》。该著作对后世的数学家和哲学家产生了深远影响。