Рубрики

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

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

Примеры:

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

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

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

В этом посте обсуждается другой подход, который не требует вычисления 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 ++ программа для поиска 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
?>


Выход:

420

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

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

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

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

0.00 (0%) 0 votes