在不使用GCD的情况下查找两个以上（或数组）数字的LCM

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#
的PHP

给定一个正整数数组, 找到数组中存在的元素的LCM。
例子：

Input : arr[] = {1, 2, 3, 4, 28}Output : 84Input: arr[] = {4, 6, 12, 24, 30}Output : 120

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。我们已经讨论过使用GCD的阵列的LCM.
【在不使用GCD的情况下查找两个以上（或数组）数字的LCM】本文讨论了一种无需计算GCD的其他方法。以下是步骤。

初始化结果= 1
查找两个或更多数组元素的公因子。
将结果乘以公因数, 然后将所有数组元素除以该公因数。
当存在两个或更多元素的公因数时, 重复步骤2和3。
将结果乘以减少(或分割)的数组元素。

插图：

Let we have to find the LCM of arr[] = {1, 2, 3, 4, 28}We initialize result = 1.2 is a common factor that appears intwo or more elements. We divide allmultiples by two and multiply resultwith 2.arr[] = {1, 1, 3, 2, 14}result = 22 is again a common factor that appears in two or more elements. We divide allmultiples by two and multiply resultwith 2.arr[] = {1, 1, 3, 1, 7}result = 4Now there is no common factor that appearsin two or more array elements. We multiplyall modified array elements with result, weget.result = 4 * 1 * 1 * 3 * 1 * 7= 84

下面是上述算法的实现。
C ++

// C++ program to find LCM of array without // using GCD. #include< bits/stdc++.h> using namespace std; // Returns LCM of arr[0..n-1] unsigned long long int LCM( int arr[], int n) { // Find the maximum value in arr[] int max_num = 0; for ( int i=0; i< n; i++) if (max_num < arr[i]) max_num = arr[i]; // Initialize result unsigned long long int res = 1; // Find all factors that are present in // two or more array elements. int x = 2; // Current factor. while (x < = max_num) { // To store indexes of all array // elements that are divisible by x. vector< int > indexes; for ( int j=0; j< n; j++) if (arr[j]%x == 0) indexes.push_back(j); // If there are 2 or more array elements // that are divisible by x. if (indexes.size() > = 2) { // Reduce all array elements divisible // by x. for ( int j=0; j< indexes.size(); j++) arr[indexes[j]] = arr[indexes[j]]/x; res = res * x; } else x++; }// Then multiply all reduced array elements for ( int i=0; i< n; i++) res = res*arr[i]; return res; }// Driver code int main() { int arr[] = {1, 2, 3, 4, 5, 10, 20, 35}; int n = sizeof (arr)/ sizeof (arr[0]); cout < < LCM(arr, n) < < "\n" ; return 0; }

Java

import java.util.Vector; // Java program to find LCM of array without // using GCD. class GFG {// Returns LCM of arr[0..n-1] static long LCM( int arr[], int n) { // Find the maximum value in arr[] int max_num = 0 ; for ( int i = 0 ; i < n; i++) { if (max_num < arr[i]) { max_num = arr[i]; } }// Initialize result long res = 1 ; // Find all factors that are present in // two or more array elements. int x = 2 ; // Current factor. while (x < = max_num) { // To store indexes of all array // elements that are divisible by x. Vector< Integer> indexes = new Vector< > (); for ( int j = 0 ; j < n; j++) { if (arr[j] % x == 0 ) { indexes.add(indexes.size(), j); } }// If there are 2 or more array elements // that are divisible by x. if (indexes.size() > = 2 ) { // Reduce all array elements divisible // by x. for ( int j = 0 ; j < indexes.size(); j++) { arr[indexes.get(j)] = arr[indexes.get(j)] / x; }res = res * x; } else { x++; } }// Then multiply all reduced array elements for ( int i = 0 ; i < n; i++) { res = res * arr[i]; }return res; }// Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 10 , 20 , 35 }; int n = arr.length; System.out.println(LCM(arr, n)); } }

Python3

# Python3 program to find LCM of array # without using GCD.# Returns LCM of arr[0..n-1] def LCM(arr, n):# Find the maximum value in arr[] max_num = 0 ; for i in range (n): if (max_num < arr[i]): max_num = arr[i]; # Initialize result res = 1 ; # Find all factors that are present # in two or more array elements. x = 2 ; # Current factor. while (x < = max_num):# To store indexes of all array # elements that are divisible by x. indexes = []; for j in range (n): if (arr[j] % x = = 0 ): indexes.append(j); # If there are 2 or more array # elements that are divisible by x. if ( len (indexes) > = 2 ):# Reduce all array elements # divisible by x. for j in range ( len (indexes)): arr[indexes[j]] = int (arr[indexes[j]] / x); res = res * x; else : x + = 1 ; # Then multiply all reduced # array elements for i in range (n): res = res * arr[i]; return res; # Driver code arr = [ 1 , 2 , 3 , 4 , 5 , 10 , 20 , 35 ]; n = len (arr); print (LCM(arr, n)); # This code is contributed by chandan_jnu

// C# program to find LCM of array // without using GCD. using System; using System.Collections; class GFG { // Returns LCM of arr[0..n-1] static long LCM( int []arr, int n) { // Find the maximum value in arr[] int max_num = 0; for ( int i = 0; i < n; i++) { if (max_num < arr[i]) { max_num = arr[i]; } } // Initialize result long res = 1; // Find all factors that are present // in two or more array elements. int x = 2; // Current factor. while (x < = max_num) { // To store indexes of all array // elements that are divisible by x. ArrayList indexes = new ArrayList(); for ( int j = 0; j < n; j++) { if (arr[j] % x == 0) { indexes.Add(j); } } // If there are 2 or more array elements // that are divisible by x. if (indexes.Count > = 2) { // Reduce all array elements divisible // by x. for ( int j = 0; j < indexes.Count; j++) { arr[( int )indexes[j]] = arr[( int )indexes[j]] / x; } res = res * x; } else { x++; } } // Then multiply all reduced // array elements for ( int i = 0; i < n; i++) { res = res * arr[i]; } return res; } // Driver code public static void Main() { int []arr = {1, 2, 3, 4, 5, 10, 20, 35}; int n = arr.Length; Console.WriteLine(LCM(arr, n)); } } // This code is contributed by mits

的PHP

< ?php // PHP program to find LCM of array // without using GCD.// Returns LCM of arr[0..n-1] function LCM( $arr , $n ) { // Find the maximum value in arr[] $max_num = 0; for ( $i = 0; $i < $n ; $i ++) if ( $max_num < $arr [ $i ]) $max_num = $arr [ $i ]; // Initialize result $res = 1; // Find all factors that are present // in two or more array elements. $x = 2; // Current factor. while ( $x < = $max_num ) { // To store indexes of all array // elements that are divisible by x. $indexes = array (); for ( $j = 0; $j < $n ; $j ++) if ( $arr [ $j ] % $x == 0) array_push ( $indexes , $j ); // If there are 2 or more array // elements that are divisible by x. if ( count ( $indexes ) > = 2) { // Reduce all array elements // divisible by x. for ( $j = 0; $j < count ( $indexes ); $j ++) $arr [ $indexes [ $j ]] = (int)( $arr [ $indexes [ $j ]] / $x ); $res = $res * $x ; } else $x ++; }// Then multiply all reduced // array elements for ( $i = 0; $i < $n ; $i ++) $res = $res * $arr [ $i ]; return $res ; }// Driver code $arr = array (1, 2, 3, 4, 5, 10, 20, 35); $n = count ( $arr ); echo LCM( $arr , $n ) . "\n" ; // This code is contributed by chandan_jnu ?>

输出如下：