如何使用递归或任何其他方法实现 L.C.M (1 to N),N>2？

Question

我一直在尝试通过质因数分解在 C 语言中实现 L.C.M(1,2,....,20)。我搜索了整个 Google 但它们只是两个变量的方法。我写了这段代码：

int lcm(int a[i],int n)
{
//n is the nth number to find L.C.M, for eg: LCM(1,2,...,20) Here,N=20
//a[i] is the list of primes upto n;
     K=sqrt(n);
     while(pow(a[i],k)>n)
         K=K-1;
     P=P*pow(a[i],k);
/*My idea over here is to make a list of primes up to 'n' and store them in list a[i]. Then for each each prime in the list,the power of that prime should exceed 'n'.
For eg: Let, N=10 .. K=3 ,
             Pow(2,3)=8<10
So,P=1*8,and for the remaining primes {3,5,7},it can be represented in prime factorization:
P=2^3 * 3^2 * 5^1 * 7^1 = 2520.
}*/

我在实现它时遇到了问题，因为我对数组了解不多，而且我认为这个算法效率不高。我对使用递归或任何其他有效方法查找 LCM（1 到 N）非常感兴趣 way.Please 求助！

Answer 1

质数分解不是计算 lcm(a,b) 的有效方法。实现它的一个好方法是使用公式：

lcm(a,b) = a / gcd(a,b) * b

现在，计算 gcd(a,b) 的简单而有效的算法如下：

Set n := a; m := b.
While {n != 0} do {s := n. n := m % m. m := s}.
Return abs(m)

其中m % n表示取模，即余数取模n.

现在我们知道如何计算 lcm(a,b) 我们可以递归地进行：

lcm(a[i],k)
    if k = 1
      Return a[0] / gcd(a[0],a[1]) * a[1]
    else
      Return lcm(lcm(a[i],k-1),a[k])

Answer 2

可能最快的方法是了解 LCM.

的两个属性

LCM 是关联的。这意味着 LCM(a,b,c) = LCM(LCM(a,b),c)。这使您可以找到大量数字的 LCM，而只计算其中两个数字的 LCM。基本上，您从 L = 1 开始，然后循环 i=1 到 20 和 L = LCM(L, i).
LCM(x,y)*GCD(x,y) == x*y，表示LCM(x,y) == x*y/GCD(x,y)。 Euclid's algorithm for GCD 比因式分解更快，因此您可以使用它来快速计算 LCM。

有了这两个属性，您应该能够设计一个快速的LCM系统，而无需任何复杂的数据结构或算法。

这是案例 [1, 2... 20] 的代码片段的框架。

int L = 1;
for(int i = 1; i <=20; i++){
    L = LCM(L,i);
}
// L contains the LCM of 1 to 20

如何使用递归或任何其他方法实现 L.C.M (1 to N),N>2？

How do I implement L.C.M (1 to N),N>2, using recursion or any other method?

c

math

recursion