Рубрики

Основные факторы LCM элементов массива

Учитывая массив arr [] такой, что 1 <= arr [i] <= 10 ^ 12, задача состоит в том, чтобы найти простые множители LCM элементов массива.

Примеры:

Input  : arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output : 2 3 5 7
// LCM of n elements is 840 and 840 = 2*2*2*3*5*7 
// so prime factors would be 2, 3, 5, 7

Input  : arr[] = {20, 10, 15, 60}
Output : 2 3 5
// LCM of n elements is 60 and 60 = 2*2*3*5,
// so prime factors would be 2,3,5

Простое решение этой проблемы — найти LCM из n элементов в массиве. Сначала инициализируйте lcm = 1, затем выполните итерацию для каждого элемента в массиве и найдите lcm предыдущего результата с новым элементом, используя формулу LCM (a, b) = (a * b) / gcd (a, b), т. Е. Lcm = (lcm * arr [i]) / gcd (lcm, arr [i]). После нахождения LCM всех n элементов мы можем вычислить все простые множители LCM.

Так как здесь ограничения велики, мы не можем реализовать описанный выше метод для решения этой проблемы, потому что при вычислении LCM (a, b) нам нужно вычислить a * b, и если a, b оба имеют значение 10 ^ 12, поэтому оно превысит предел целого размера. Мы перейдем к этой проблеме по-другому, используя сито сундарам и простую факторизацию числа. Как мы знаем, если LCM (a, b) = k, то любой простой фактор a или b также будет основным фактором k.

  • Возьмите коэффициент массива [] размера 10 ^ 6 и инициализируйте его 0, потому что простой множитель любого числа всегда меньше и равен его квадратному корню и в нашем ограничении arr [i] <= 10 ^ 12.
  • Создайте все простые числа, меньшие и равные 10 ^ 6, и сохраните их в другом массиве.
  • Теперь один за другим вычислите все простые множители каждого числа в массиве и отметьте их как 1 в массиве factor [].
  • Теперь просмотрите массив [] и распечатайте все индексы, которые помечены как 1, потому что это будут простые множители lcm из n чисел в данном массиве.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска простых факторов LCM элементов массива
#include <bits/stdc++.h>

using namespace std;

  

const int MAX  = 1000000;

typedef long long int ll;

  
// массив для хранения всех простых чисел, меньших и равных 10 ^ 6

vector <int> primes;

  
// функция полезности для сита сундарам

void sieve()

{

    int n = MAX;

  

    // В общем сито сундарам, производит простые числа меньше

    // чем (2 * x + 2) для числа данного числа x. поскольку

    // мы хотим, чтобы простые числа были меньше n, мы уменьшаем n до половины

    int nNew = (n)/2;

  

    // Этот массив используется для разделения чисел вида

    // i + j + 2ij от других, где 1 <= i <= j

    bool marked[nNew + 100];

  

    // Инициализируем все элементы как не отмеченные

    memset(marked, false, sizeof(marked));

  

    // Основная логика сундарама. Отметьте все номера, которые не

    // генерируем простое число, выполняя 2 * i + 1

    int tmp=sqrt(n);

    for (int i=1; i<=(tmp-1)/2; i++)

        for (int j=(i*(i+1))<<1; j<=nNew; j=j+2*i+1)

            marked[j] = true;

  

    // Поскольку 2 - простое число

    primes.push_back(2);

  

    // Распечатать другие простые числа. Оставшиеся простые числа имеют вид

    // 2 * i + 1 такой, что отмеченный [i] является ложным.

    for (int i=1; i<=nNew; i++)

        if (marked[i] == false)

            primes.push_back(2*i + 1);

}

  
// Функция для поиска простых множителей n элементов
// данный массив

void primeLcm(ll arr[], int n )

{

    // factor [] -> массив, чтобы отметить все основные факторы

    // lcm элементов массива

    int factors[MAX] = {0};

  

    // Один за другим вычисляем простые множители числа

    // и помечаем их в массиве factor []

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

    {

        // копировать -> дублировать оригинальный элемент в

        // выполнить операцию

        ll copy = arr[i];

  

        // sqr -> квадратный корень текущего числа 'copy'

        // потому что все главные факторы всегда меньше

        // чем и равно квадратному корню из данного числа

        int sqr = sqrt(copy);

  

        // проверка делимости с простым множителем

        for (int j=0; primes[j]<=sqr; j++)

        {

            // если текущее простое число является фактором 'copy'

            if (copy%primes[j] == 0)

            {

                // делим с текущим простым множителем до

                // это может разделить число

                while (copy%primes[j] == 0)

                    copy = copy/primes[j];

  

                // помечаем текущий простой множитель как 1 в

                // массив [множители]

                factors[primes[j]] = 1;

            }

        }

  

        // После вычисления показателей всех простых факторов

        // либо значение 'copy' будет равно 1 из-за

        // полная делимость или оставшееся значение

        // 'copy' будет, конечно, простым, поэтому мы будем

        // также помечаем это простое число как фактор

        if (copy > 1)

            factors[copy] = 1;

    }

  

    // если 2 является простым множителем lcm всех элементов

    // в данном массиве

    if (factors[2] == 1)

        cout << 2 << " ";

  

    // переходим к выводу всех простых множителей lcm

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

    for (int i=3; i<=MAX; i=i+2)

        if (factors[i] == 1)

            cout << i << " ";

}

  
// Драйвер программы для запуска дела

int main()

{

    sieve();

    ll arr[] = {20, 10, 15, 60};

    int n = sizeof(arr)/sizeof(arr[0]);

    primeLcm(arr, n);

    return 0;

}

Джава

// Java-программа для поиска простых чисел
// факторы LCM элементов массива

import java.util.*;

  

class GFG

{

  

static int MAX = 1000000;

  
// массив для хранения всего простого меньше
// чем и равен 10 ^ 6

static ArrayList<Integer> primes = new ArrayList<Integer>();

  
// функция полезности для сита сундарам

static void sieve()

{

    int n = MAX;

  

    // В общем сито сундарам,

    // производит простые числа меньше

    // (2 * x + 2) для заданного числа

    // номер х. Так как мы хотим простые числа

    // меньше n, мы уменьшаем n до половины

    int nNew = (n) / 2;

  

    // Этот массив используется для разделения

    // числа вида i + j + 2ij

    // от других, где 1 <= i <= j

    boolean[] marked = new boolean[nNew + 100];

  

  

    // Основная логика сундарама. пометить все

    // числа, которые не генерируют

    // простое число, выполнив 2 * i + 1

    int tmp = (int)Math.sqrt(n);

    for (int i = 1; i <= (tmp - 1) / 2; i++)

        for (int j = (i * (i + 1)) << 1

                j <= nNew; j = j + 2 * i + 1)

            marked[j] = true;

  

    // Поскольку 2 - простое число

    primes.add(2);

  

    // Распечатать другие простые числа. остальной

    // простые числа имеют вид 2 * i + 1

    // такой, что отмеченный [i] является ложным.

    for (int i = 1; i <= nNew; i++)

        if (marked[i] == false)

            primes.add(2 * i + 1);

}

  
// Функция для поиска простых факторов
// из n элементов данного массива

static void primeLcm(int[] arr, int n )

{

    // factor [] -> массив, чтобы отметить все простые

    // факторы lcm элементов массива

    int[] factors = new int[MAX];

  

    // Один за другим вычисляем простые множители числа

    // и помечаем их в массиве factor []

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

    {

        // копировать -> дублировать оригинальный элемент в

        // выполнить операцию

        int copy = arr[i];

  

        // sqr -> квадратный корень текущего числа 'copy'

        // потому что все главные факторы всегда меньше

        // чем и равно квадратному корню из данного числа

        int sqr = (int)Math.sqrt(copy);

  

        // проверка делимости с простым множителем

        for (int j = 0; primes.get(j) <= sqr; j++)

        {

            // если текущее простое число является фактором 'copy'

            if (copy % primes.get(j) == 0)

            {

                // делим с текущим простым множителем до

                // это может разделить число

                while (copy % primes.get(j) == 0)

                    copy = copy / primes.get(j);

  

                // помечаем текущий простой множитель как 1 в

                // массив [множители]

                factors[primes.get(j)] = 1;

            }

        }

  

        // После вычисления показателей всех простых факторов

        // либо значение 'copy' будет равно 1 из-за

        // полная делимость или оставшееся значение

        // 'copy' будет, конечно, простым, поэтому мы будем

        // также помечаем это простое число как фактор

        if (copy > 1)

            factors[copy] = 1;

    }

  

    // если 2 является простым множителем lcm всех элементов

    // в данном массиве

    if (factors[2] == 1)

        System.out.print("2 ");

  

    // переходим к выводу всех простых множителей lcm

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

    for (int i = 3; i <= MAX; i = i + 2)

        if (factors[i] == 1)

            System.out.print(i+" ");

}

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

public static void main (String[] args)

{

    sieve();

    int[] arr = {20, 10, 15, 60};

    int n = arr.length;

    primeLcm(arr, n);

}
}

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

python3

# Python3 программа для поиска простых факторов
# LCM элементов массива

import math;

MAX = 10000

  
# массив для хранения всего простого меньше чем
# и равно 10 ^ 6

primes = []; 

  
# функция полезности для сита сундарам

def sieve(): 

  

    n = MAX

  

    # В общем Сито Сундарам, производит

    # простых чисел меньше (2 * x + 2) для

    # номер заданный номер x. Так как мы хотим

    # простых чисел меньше n, мы уменьшаем n до половины

    nNew = int(n / 2); 

  

    # Этот массив используется для разделения чисел

    # форма i + j + 2ij от других, где 1 <= i <= j

    marked = [False] * (nNew + 100); 

  

  

    # Основная логика Сундарама. Отметить все номера

    # которые не генерируют простое число

    # делаю 2 * я + 1

    tmp = int(math.sqrt(n)); 

    for i in range(1, int((tmp - 1) / 2) + 1): 

        for j in range((i * (i + 1)) << 1

                        nNew + 1, 2 * i + 1): 

            marked[j] = True

  

    # Так как 2 - простое число

    primes.append(2); 

  

    # Распечатать другие простые числа. Оставшиеся простые числа

    # имеют форму 2 * i + 1, такую что

    # отмечен [я] ложь.

    for i in range(1, nNew + 1): 

        if (marked[i] == False): 

            primes.append(2 * i + 1); 

  
# Функция для поиска основных факторов
# n элементов данного массива

def primeLcm(arr, n ): 

  

    # factor [] -> массив, чтобы отметить все простые

    # факторы lcm элементов массива

    factors = [0] * (MAX); 

  

    # Один за другим рассчитать основные факторы

    # номер и пометить их в массиве factor []

    for i in range(n):

          

        # копия -> копия оригинала

        # элемент для выполнения операции

        copy = arr[i]; 

  

        # sqr -> квадратный корень текущего числа

        # «Копировать», потому что все основные факторы

        # всегда меньше и равно квадрату

        # корень данного числа

        sqr = int(math.sqrt(copy)); 

  

        # проверить делимость с помощью простого множителя

        j = 0;

        while (primes[j] <= sqr): 

          

            # если текущее простое число

            # фактор «копирования»

            if (copy % primes[j] == 0): 

                  

                # делить с текущим простым множителем

                # пока он не разделит число

                while (copy % primes[j] == 0): 

                    copy = int(copy / primes[j]); 

  

                # пометить текущий простой коэффициент как 1

                # в массиве факторов []

                factors[primes[j]] = 1

            j += 1

  

        # После расчета показателей всех простых чисел

        # факторы либо значение 'copy' будет равно 1

        # из-за полной делимости или

        # оставшееся значение 'copy' будет обязательно

        # простое число, поэтому мы также отметим это простое число

        # как фактор

        if (copy > 1): 

            factors[copy] = 1

  

    # если 2 является основным множителем lcm

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

    if (factors[2] == 1): 

        print("2 ", end = ""); 

  

    # Пройдите для печати всех основных факторов

    # lcm всех элементов в данном массиве

    for i in range(3, MAX + 1, 2): 

        if (factors[i] == 1): 

            print(i, end = " "); 

  
Код водителя
sieve(); 

arr = [20, 10, 15, 60]; 

n = len(arr); 

primeLcm(arr, n);

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

C #

// C # программа для поиска простых чисел
// факторы LCM элементов массива

using System;

using System.Collections;

  

class GFG

{

  

static int MAX = 1000000;

  
// массив для хранения всего простого меньше
// чем и равен 10 ^ 6

static ArrayList primes = new ArrayList();

  
// функция полезности для сита сундарам

static void sieve()

{

    int n = MAX;

  

    // В общем сито сундарам,

    // производит простые числа меньше

    // (2 * x + 2) для заданного числа

    // номер х. Так как мы хотим простые числа

    // меньше n, мы уменьшаем n до половины

    int nNew = (n) / 2;

  

    // Этот массив используется для разделения

    // числа вида i + j + 2ij

    // от других, где 1 <= i <= j

    bool[] marked = new bool[nNew + 100];

  

  

    // Основная логика сундарама. пометить все

    // числа, которые не генерируют

    // простое число, выполнив 2 * i + 1

    int tmp = (int)Math.Sqrt(n);

    for (int i = 1; i <= (tmp - 1) / 2; i++)

        for (int j = (i * (i + 1)) << 1; 

                j <= nNew; j = j + 2 * i + 1)

            marked[j] = true;

  

    // Поскольку 2 - простое число

    primes.Add(2);

  

    // Распечатать другие простые числа. остальной

    // простые числа имеют вид 2 * i + 1

    // такой, что отмеченный [i] является ложным.

    for (int i = 1; i <= nNew; i++)

        if (marked[i] == false)

            primes.Add(2 * i + 1);

}

  
// Функция для поиска простых факторов
// из n элементов данного массива

static void primeLcm(int[] arr, int n )

{

    // factor [] -> array to

    // отметить все основные факторы

    // lcm элементов массива

    int[] factors = new int[MAX];

  

    // Один за другим вычисляем простое число

    // факторы числа и марки

    // их в массиве factor []

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

    {

        // копия -> копия оригинала

        // элемент для выполнения операции

        int copy = arr[i];

  

        // sqr -> квадратный корень текущего

        // число «копия», потому что все простые

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

        // равно квадратному корню данного числа

        int sqr = (int)Math.Sqrt(copy);

  

        // проверка делимости с простым множителем

        for (int j = 0; (int)primes[j] <= sqr; j++)

        {

            // если текущее простое число является фактором 'copy'

            if (copy % (int)primes[j] == 0)

            {

                // делим с текущим простым множителем до

                // это может разделить число

                while (copy % (int)primes[j] == 0)

                    copy = copy / (int)primes[j];

  

                // помечаем текущий простой множитель как 1 в

                // массив [множители]

                factors[(int)primes[j]] = 1;

            }

        }

  

        // После вычисления показателей всех простых факторов

        // либо значение 'copy' будет равно 1 из-за

        // полная делимость или оставшееся значение

        // 'copy' будет, конечно, простым, поэтому мы будем

        // также помечаем это простое число как фактор

        if (copy > 1)

            factors[copy] = 1;

    }

  

    // если 2 является простым множителем lcm всех элементов

    // в данном массиве

    if (factors[2] == 1)

        Console.Write("2 ");

  

    // переходим к выводу всех простых множителей lcm

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

    for (int i = 3; i <= MAX; i = i + 2)

        if (factors[i] == 1)

            Console.Write(i+" ");

}

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

static void Main()

{

    sieve();

    int[] arr = {20, 10, 15, 60};

    int n = arr.Length;

    primeLcm(arr, n);

}
}

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

PHP

<?php
// PHP программа для поиска простых факторов
// LCM элементов массива

  

$MAX = 10000; 

  
// массив для хранения всего простого меньше
// и равно 10 ^ 6

$primes = array(); 

  
// функция полезности для сита сундарам

function sieve() 

{

    global $MAX, $primes;

    $n = $MAX

  

    // В общем сито сундарам, производит

    // простые числа меньше (2 * x + 2) для числа

    // заданное число х. Так как мы хотим, чтобы простые числа были меньше

    // чем n, мы уменьшаем n до половины

    $nNew = (int)($n / 2); 

  

    // Этот массив используется для разделения чисел

    // форма i + j + 2ij от других, где 1 <= i <= j

    $marked = array_fill(0, $nNew + 100, false); 

  

  

    // Основная логика сундарама. Отметьте все числа, которые

    // не генерируем простое число, выполняя 2 * i + 1

    $tmp = (int)sqrt($n); 

    for ($i = 1; $i <= (int)(($tmp - 1) / 2); $i++) 

        for ($j = ($i * ($i + 1)) << 1;

             $j <= $nNew; $j = $j + 2 * $i + 1) 

            $marked[$j] = true; 

  

    // Поскольку 2 - простое число

    array_push($primes, 2); 

  

    // Распечатать другие простые числа. Оставшиеся простые числа

    // форма 2 * i + 1 такая, что отмеченная [i] ложна.

    for ($i = 1; $i <= $nNew; $i++) 

        if ($marked[$i] == false) 

            array_push($primes, 2 * $i + 1); 

  
// Функция для поиска простых множителей n
// элементы данного массива

function primeLcm($arr, $n

{

    global $MAX, $primes;

      

    // factor [] -> массив, чтобы отметить все простые

    // факторы lcm элементов массива

    $factors = array_fill(0, $MAX, 0); 

  

    // Один за другим вычисляем простые множители

    // нумеруем и помечаем их в массиве factor []

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

    

        // копия -> копия оригинала

        // элемент для выполнения операции

        $copy = $arr[$i]; 

  

        // sqr -> квадратный корень текущего числа

        // «копировать», потому что все основные факторы

        // всегда меньше и равно квадрату

        // корень данного числа

        $sqr = (int)sqrt($copy); 

  

        // проверка делимости с простым множителем

        for ($j = 0; $primes[$j] <= $sqr; $j++) 

        

            // если текущее простое число является множителем

            // of 'copy'

            if ($copy % $primes[$j] == 0) 

            

                // делим с текущим простым множителем

                // пока не разделим число

                while ($copy % $primes[$j] == 0) 

                    $copy = (int)($copy / $primes[$j]); 

  

                // помечаем текущий простой множитель как 1

                // в массиве factor []

                $factors[$primes[$j]] = 1; 

            

        

  

        // После вычисления показателей всех простых чисел

        // факторы либо значение 'copy' будет равно 1

        // из-за полной делимости или оставшихся

        // значение 'copy', безусловно, будет простым, поэтому

        // мы также отметим это простое число как фактор

        if ($copy > 1) 

            $factors[$copy] = 1; 

    

  

    // если 2 является основным множителем lcm всех

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

    if ($factors[2] == 1) 

        echo "2 "

  

    // переходим к выводу всех простых факторов

    // lcm всех элементов в данном массиве

    for ($i = 3; $i <= $MAX; $i = $i + 2) 

        if ($factors[$i] == 1) 

            echo $i . " "

  
// Код драйвера
sieve(); 

$arr = array(20, 10, 15, 60); 

$n = count($arr); 

primeLcm($arr, $n);

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


Выход:

2 3 5

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

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

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

Основные факторы LCM элементов массива

0.00 (0%) 0 votes