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

我一直在尝试用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）很感兴趣。请帮忙！

最佳答案

可能最快的方法是了解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

关于c - 如何使用递归或任何其他方法实现L.C.M(1到N)，N> 2？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28931337/