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

2021年3月22日15:24:46 发表评论 726 次浏览

本文概述

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

例子：

Input : arr[] = {1, 2, 3, 4, 28}
Output : 84

Input  : arr[] = {4, 6, 12, 24, 30}
Output : 120

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

我们已经讨论过使用GCD的阵列的LCM.

本文讨论了一种无需计算GCD的其他方法。以下是步骤。

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

插图：

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 in
two or more elements. We divide all
multiples by two and multiply result
with 2.
arr[] = {1, 1, 3, 2, 14}
result = 2

2 is again a common factor that appears 
in two or more elements. We divide all
multiples by two and multiply result
with 2.
arr[] = {1, 1, 3, 1, 7}
result = 4

Now there is no common factor that appears
in two or more array elements. We multiply
all modified array elements with result, we
get.
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#

// 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
?>

输出如下：

420

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: