Нахождение LCM из более чем двух (или массив) чисел без использования GCD

31.12.2019Математика

По массиву натуральных чисел найдите LCM элементов, присутствующих в массиве.

Примеры:

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

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

Мы обсудили LCM массива с использованием GCD .

В этом посте обсуждается другой подход, который не требует вычисления 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 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 ++ программа для поиска LCM массива без
// используя GCD.
#include<bits/stdc++.h>

using namespace std;

// Возвращает LCM arr [0..n-1]

unsigned long long int LCM(int arr[], int n)

{

// Находим максимальное значение в arr []

int max_num = 0;

for (int i=0; i<n; i++)

if (max_num < arr[i])

max_num = arr[i];

// Инициализировать результат

unsigned long long int res = 1;

// Найти все факторы, которые присутствуют в

// два или более элемента массива.

int x = 2; // Текущий фактор.

while (x <= max_num)

{

// Хранить индексы всего массива

// элементы, которые делятся на х.

vector<int> indexes;

for (int j=0; j<n; j++)

if (arr[j]%x == 0)

indexes.push_back(j);

// Если есть 2 или более элементов массива

// которые делятся на х.

if (indexes.size() >= 2)

{

// Уменьшаем все элементы массива делимые

// по х.

for (int j=0; j<indexes.size(); j++)

arr[indexes[j]] = arr[indexes[j]]/x;

res = res * x;

}

else

x++;

}

// Затем умножаем все уменьшенные элементы массива

for (int i=0; i<n; i++)

res = res*arr[i];

return res;

}

// Код драйвера

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;

}

Джава

import java.util.Vector;

// Java программа для поиска LCM массива без
// используя GCD.

class GFG {

// Возвращает LCM arr [0..n-1]

static long LCM(int arr[], int n) {

// Находим максимальное значение в arr []

int max_num = 0;

for (int i = 0; i < n; i++) {

if (max_num < arr[i]) {

max_num = arr[i];

}

// Инициализировать результат

long res = 1;

// Найти все факторы, которые присутствуют в

// два или более элемента массива.

int x = 2; // Текущий фактор.

while (x <= max_num) {

// Хранить индексы всего массива

// элементы, которые делятся на х.

Vector<Integer> indexes = new Vector<>();

for (int j = 0; j < n; j++) {

if (arr[j] % x == 0) {

indexes.add(indexes.size(), j);

}

// Если есть 2 или более элементов массива

// которые делятся на х.

if (indexes.size() >= 2) {

// Уменьшаем все элементы массива делимые

// по х.

for (int j = 0; j < indexes.size(); j++) {

arr[indexes.get(j)] = arr[indexes.get(j)] / x;

}

res = res * x;

} else {

x++;

}

// Затем умножаем все уменьшенные элементы массива

for (int i = 0; i < n; i++) {

res = res * arr[i];

}

return res;

}

// Код драйвера

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

# Pyhton3 программа для поиска LCM массива
# без использования GCD.

# Возвращает LCM arr [0..n-1]

def LCM(arr, n):

# Найти максимальное значение в arr []

max_num = 0;

for i in range(n):

if (max_num < arr[i]):

max_num = arr[i];

# Инициализировать результат

res = 1;

# Найти все факторы, которые присутствуют

# в двух или более элементах массива.

x = 2; # Текущий фактор.

while (x <= max_num):

# Хранить индексы всего массива

# элементы, которые делятся на х.

indexes = [];

for j in range(n):

if (arr[j] % x == 0):

indexes.append(j);

# Если есть 2 или более массив

# элементы, которые делятся на х.

if (len(indexes) >= 2):

# Уменьшить все элементы массива

# делится на х.

for j in range(len(indexes)):

arr[indexes[j]] = int(arr[indexes[j]] / x);

res = res * x;

else:

x += 1;

# Затем умножьте все уменьшенное

# элементы массива

for i in range(n):

res = res * arr[i];

return res;

# Код драйвера

arr = [1, 2, 3, 4, 5, 10, 20, 35];

n = len(arr);

print(LCM(arr, n));

# Этот код предоставлен chandan_jnu

C #

// C # программа для поиска LCM массива
// без использования GCD.

using System;

using System.Collections;

class GFG

{

// Возвращает LCM arr [0..n-1]

static long LCM(int []arr, int n)

{

// Находим максимальное значение в arr []

int max_num = 0;

for (int i = 0; i < n; i++)

{

if (max_num < arr[i])

{

max_num = arr[i];

}

// Инициализировать результат

long res = 1;

// Найти все факторы, которые присутствуют

// в двух или более элементах массива.

int x = 2; // Текущий фактор.

while (x <= max_num)

{

// Хранить индексы всего массива

// элементы, которые делятся на х.

ArrayList indexes = new ArrayList();

for (int j = 0; j < n; j++)

{

if (arr[j] % x == 0)

{

indexes.Add(j);

}

// Если есть 2 или более элементов массива

// которые делятся на х.

if (indexes.Count >= 2)

{

// Уменьшаем все элементы массива делимые

// по х.

for (int j = 0; j < indexes.Count; j++)

{

arr[(int)indexes[j]] = arr[(int)indexes[j]] / x;

}

res = res * x;

} else

{

x++;

}

// Затем умножаем все уменьшенное

// элементы массива

for (int i = 0; i < n; i++)

{

res = res * arr[i];

}

return res;

}

// Код драйвера

public static void Main()

{

int []arr = {1, 2, 3, 4, 5, 10, 20, 35};

int n = arr.Length;

Console.WriteLine(LCM(arr, n));

}
}

// Этот код предоставлен mits

PHP

<?php
// PHP-программа для поиска LCM массива
// без использования GCD.

// Возвращает LCM arr [0..n-1]

function LCM($arr, $n)

{

// Находим максимальное значение в arr []

$max_num = 0;

for ($i = 0; $i < $n; $i++)

if ($max_num < $arr[$i])

$max_num = $arr[$i];

// Инициализировать результат

$res = 1;

// Найти все факторы, которые присутствуют

// в двух или более элементах массива.

$x = 2; // Текущий фактор.

while ($x <= $max_num)

{

// Хранить индексы всего массива

// элементы, которые делятся на х.

$indexes = array();

for ($j = 0; $j < $n; $j++)

if ($arr[$j] % $x == 0)

array_push($indexes, $j);

// Если есть 2 или более массив

// элементы, которые делятся на х.

if (count($indexes) >= 2)

{

// Уменьшаем все элементы массива

// делится на х.

for ($j = 0; $j < count($indexes); $j++)

$arr[$indexes[$j]] = (int)($arr[$indexes[$j]] / $x);

$res = $res * $x;

}

else

$x++;

}

// Затем умножаем все уменьшенное

// элементы массива

for ($i = 0; $i < $n; $i++)

$res = $res * $arr[$i];

return $res;

}

// Код драйвера

$arr = array(1, 2, 3, 4, 5, 10, 20, 35);

$n = count($arr);

echo LCM($arr, $n) . "\n";

// Этот код предоставлен chandan_jnu
?>

Выход:

Эта статья предоставлена Адитьей Кумаром . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Нахождение LCM из более чем двух (или массив) чисел без использования GCD

0.00 (0%) 0 votes