给定一个由n个数字组成的数组，找到其中的LCM。
null
Input : {1, 2, 8, 3}Output : 24Input : {2, 7, 3, 9, 4}Output : 252
我们知道， 
上述关系仅适用于两个数字， 
这里的想法是将我们的关系扩展到两个以上的数字。假设我们有一个数组arr[]，它包含n个需要计算LCM的元素。 我们算法的主要步骤是：
- 初始化ans=arr[0]。
- 迭代数组的所有元素，即从i=1到i=n-1 在第i次迭代中，ans=LCM（arr[0]，arr[1]，…..，arr[i-1]）。这很容易做到 LCM（arr[0]，arr[1]，..，arr[i]）=LCM（ans，arr[i]） .因此，在第i次迭代中，我们只需 ans=LCM（ans，arr[i]）=ans x arr[i]/gcd（ans，arr[i]）
下面是上述算法的实现：
C++
// C++ program to find LCM of n elements #include <bits/stdc++.h> using namespace std; typedef long long int ll; // Utility function to find // GCD of 'a' and 'b' int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Returns LCM of array elements ll findlcm( int arr[], int n) { // Initialize result ll ans = arr[0]; // ans contains LCM of arr[0], ..arr[i] // after i'th iteration, for ( int i = 1; i < n; i++) ans = (((arr[i] * ans)) / (gcd(arr[i], ans))); return ans; } // Driver Code int main() { int arr[] = { 2, 7, 3, 9, 4 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "%lld" , findlcm(arr, n)); return 0; } |
JAVA
// Java Program to find LCM of n elements public class GFG { public static long lcm_of_array_elements( int [] element_array) { long lcm_of_array_elements = 1 ; int divisor = 2 ; while ( true ) { int counter = 0 ; boolean divisible = false ; for ( int i = 0 ; i < element_array.length; i++) { // lcm_of_array_elements (n1, n2, ... 0) = 0. // For negative number we convert into // positive and calculate lcm_of_array_elements. if (element_array[i] == 0 ) { return 0 ; } else if (element_array[i] < 0 ) { element_array[i] = element_array[i] * (- 1 ); } if (element_array[i] == 1 ) { counter++; } // Divide element_array by devisor if complete // division i.e. without remainder then replace // number with quotient; used for find next factor if (element_array[i] % divisor == 0 ) { divisible = true ; element_array[i] = element_array[i] / divisor; } } // If divisor able to completely divide any number // from array multiply with lcm_of_array_elements // and store into lcm_of_array_elements and continue // to same divisor for next factor finding. // else increment divisor if (divisible) { lcm_of_array_elements = lcm_of_array_elements * divisor; } else { divisor++; } // Check if all element_array is 1 indicate // we found all factors and terminate while loop. if (counter == element_array.length) { return lcm_of_array_elements; } } } // Driver Code public static void main(String[] args) { int [] element_array = { 2 , 7 , 3 , 9 , 4 }; System.out.println(lcm_of_array_elements(element_array)); } } // Code contributed by Mohit Gupta_OMG |
python
# Python Program to find LCM of n elements def find_lcm(num1, num2): if (num1>num2): num = num1 den = num2 else : num = num2 den = num1 rem = num % den while (rem ! = 0 ): num = den den = rem rem = num % den gcd = den lcm = int ( int (num1 * num2) / int (gcd)) return lcm l = [ 2 , 7 , 3 , 9 , 4 ] num1 = l[ 0 ] num2 = l[ 1 ] lcm = find_lcm(num1, num2) for i in range ( 2 , len (l)): lcm = find_lcm(lcm, l[i]) print (lcm) # Code contributed by Mohit Gupta_OMG |
C#
// C# Program to find LCM of n elements using System; public class GFG { public static long lcm_of_array_elements( int [] element_array) { long lcm_of_array_elements = 1; int divisor = 2; while ( true ) { int counter = 0; bool divisible = false ; for ( int i = 0; i < element_array.Length; i++) { // lcm_of_array_elements (n1, n2, ... 0) = 0. // For negative number we convert into // positive and calculate lcm_of_array_elements. if (element_array[i] == 0) { return 0; } else if (element_array[i] < 0) { element_array[i] = element_array[i] * (-1); } if (element_array[i] == 1) { counter++; } // Divide element_array by devisor if complete // division i.e. without remainder then replace // number with quotient; used for find next factor if (element_array[i] % divisor == 0) { divisible = true ; element_array[i] = element_array[i] / divisor; } } // If divisor able to completely divide any number // from array multiply with lcm_of_array_elements // and store into lcm_of_array_elements and continue // to same divisor for next factor finding. // else increment divisor if (divisible) { lcm_of_array_elements = lcm_of_array_elements * divisor; } else { divisor++; } // Check if all element_array is 1 indicate // we found all factors and terminate while loop. if (counter == element_array.Length) { return lcm_of_array_elements; } } } // Driver Code public static void Main() { int [] element_array = { 2, 7, 3, 9, 4 }; Console.Write(lcm_of_array_elements(element_array)); } } // This Code is contributed by nitin mittal |
PHP
<?php // PHP program to find LCM of n elements // Utility function to find // GCD of 'a' and 'b' function gcd( $a , $b ) { if ( $b == 0) return $a ; return gcd( $b , $a % $b ); } // Returns LCM of array elements function findlcm( $arr , $n ) { // Initialize result $ans = $arr [0]; // ans contains LCM of // arr[0], ..arr[i] // after i'th iteration, for ( $i = 1; $i < $n ; $i ++) $ans = ((( $arr [ $i ] * $ans )) / (gcd( $arr [ $i ], $ans ))); return $ans ; } // Driver Code $arr = array (2, 7, 3, 9, 4 ); $n = sizeof( $arr ); echo findlcm( $arr , $n ); // This code is contributed by ChitraNayal ?> |
Javascript
<script> // Javascript program to find LCM of n elements // Utility function to find // GCD of 'a' and 'b' function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Returns LCM of array elements function findlcm(arr, n) { // Initialize result let ans = arr[0]; // ans contains LCM of arr[0], ..arr[i] // after i'th iteration, for (let i = 1; i < n; i++) ans = (((arr[i] * ans)) / (gcd(arr[i], ans))); return ans; } // Driver Code let arr = [ 2, 7, 3, 9, 4 ]; let n = arr.length; document.write(findlcm(arr, n)); // This code is contributed by Mayank Tyagi </script> |
输出
252
下面是上述算法的递归实现：
C++
#include <bits/stdc++.h> using namespace std; //recursive implementation int LcmOfArray(vector< int > arr, int idx){ // lcm(a,b) = (a*b/gcd(a,b)) if (idx == arr.size()-1){ return arr[idx]; } int a = arr[idx]; int b = LcmOfArray(arr, idx+1); return (a*b/__gcd(a,b)); // __gcd(a,b) is inbuilt library function } int main() { vector< int > arr = {1,2,8,3}; cout << LcmOfArray(arr, 0) << "" ; arr = {2,7,3,9,4}; cout << LcmOfArray(arr,0) << "" ; return 0; } |
JAVA
import java.util.*; class GFG { // Recursive function to return gcd of a and b static int __gcd( int a, int b) { return b == 0 ? a:__gcd(b, a % b); } // recursive implementation static int LcmOfArray( int [] arr, int idx) { // lcm(a,b) = (a*b/gcd(a,b)) if (idx == arr.length - 1 ){ return arr[idx]; } int a = arr[idx]; int b = LcmOfArray(arr, idx+ 1 ); return (a*b/__gcd(a,b)); // } public static void main(String[] args) { int [] arr = { 1 , 2 , 8 , 3 }; System.out.print(LcmOfArray(arr, 0 )+ "" ); int [] arr1 = { 2 , 7 , 3 , 9 , 4 }; System.out.print(LcmOfArray(arr1, 0 )+ "" ); } } // This code is contributed by gauravrajput1 |
Python3
def __gcd(a, b): if (a = = 0 ): return b return __gcd(b % a, a) # recursive implementation def LcmOfArray(arr, idx): # lcm(a,b) = (a*b/gcd(a,b)) if (idx = = len (arr) - 1 ): return arr[idx] a = arr[idx] b = LcmOfArray(arr, idx + 1 ) return int (a * b / __gcd(a,b)) # __gcd(a,b) is inbuilt library function arr = [ 1 , 2 , 8 , 3 ] print (LcmOfArray(arr, 0 )) arr = [ 2 , 7 , 3 , 9 , 4 ] print (LcmOfArray(arr, 0 )) # This code is contributed by divyeshrabadiya07. |
C#
using System; class GFG { // Function to return // gcd of a and b static int __gcd( int a, int b) { if (a == 0) return b; return __gcd(b % a, a); } //recursive implementation static int LcmOfArray( int [] arr, int idx){ // lcm(a,b) = (a*b/gcd(a,b)) if (idx == arr.Length-1){ return arr[idx]; } int a = arr[idx]; int b = LcmOfArray(arr, idx+1); return (a*b/__gcd(a,b)); // __gcd(a,b) is inbuilt library function } static void Main() { int [] arr = {1,2,8,3}; Console.WriteLine(LcmOfArray(arr, 0)); int [] arr1 = {2,7,3,9,4}; Console.WriteLine(LcmOfArray(arr1,0)); } } |
Javascript
<script> // Function to return // gcd of a and b function __gcd(a, b) { if (a == 0) return b; return __gcd(b % a, a); } //recursive implementation function LcmOfArray(arr, idx){ // lcm(a,b) = (a*b/gcd(a,b)) if (idx == arr.length-1){ return arr[idx]; } let a = arr[idx]; let b = LcmOfArray(arr, idx+1); return (a*b/__gcd(a,b)); // __gcd(a,b) is inbuilt library function } let arr = [1,2,8,3]; document.write(LcmOfArray(arr, 0) + "</br>" ); arr = [2,7,3,9,4]; document.write(LcmOfArray(arr,0)); // This code is contributed by decode2207. </script> |
输出
24252
相关文章：
本文由 马杜尔·莫迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
