如何使用遞歸或其他方法實現L.C.M（1到N），N> 2？

Question

我一直試圖通過素分解實現L.C.M（1,2，...，20）的C語言。我在谷歌搜索了所有，但他們只是兩個變量的方法。 我寫這段代碼：

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）。請幫助！

Answer 1

或許要做到這一點是要知道的LCM兩個屬性的最快方式。

1. LCM是關聯的。那意味着LCM(a,b,c) = LCM(LCM(a,b),c)。這允許您查找大量數字的LCM，而只計算其中兩個的LCM。基本上，你從L = 1開始，然後循環i=1到20和L = LCM(L, i)。
2. 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 

Answer 2

總理因子分解不是計算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])