java - 需要解释循环java递归代码

Question

此代码用于查找可被 1 到 20 的所有 num 整除的最小数字

static long gcd(long a, long b) 
{ 
   if(a%b != 0)  
      return gcd(b,a%b); 
   else 
      return b; 
} 

// Function returns the lcm of first n numbers 
static long lcm(long n) 
{ 
    long ans = 1;     
    for (long i = 1; i <= n; i++) 
        ans = (ans * i)/(gcd(ans, i)); 
    return ans; 
} 

// Driver program to test the above function 
public static void main(String []args)  
{ 
    long n = 20; 
    System.out.println(lcm(n)); 

} 

标签： java

Answer 1

这是非常数学的，但 gcd 代表“最大公分母”，而 lcm 代表“最小公倍数”。

主算法跟踪当前最小公倍数“ans”，并将“i”从 1 迭代到“n”，在本例中为 20。然后将当前值乘以每个“i”并除以最大公倍数“ans”和“i”之间的分母。

gcd() 方法使用欧几里得算法计算最大公分母

算法起作用的原因更多是https://math.stackexchange.com/的问题