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

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

本文概述

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

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

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

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 ) {
}
}

// 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)
{
}
}

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