Dada una array arr[] tal que 1 <= arr[i] <= 10^12, la tarea es encontrar los factores primos de LCM de los elementos de la array.
Ejemplos:
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
Una solución simple para este problema es encontrar MCM de n elementos en una array. Primero inicialice lcm = 1, luego itere para cada elemento en la array y encuentre el mcm del resultado anterior con el nuevo elemento usando la fórmula LCM (a, b) = (a * b) / mcd (a, b) es decir, lcm = (lcm * arr[i]) / mcd(lcm, arr[i]). Después de encontrar LCM de todos los n elementos, podemos calcular todos los factores primos de LCM.
Dado que aquí las restricciones son grandes, no podemos implementar el método anterior para resolver este problema porque al calcular LCM (a, b) necesitamos calcular a * b y si a, b ambos tienen un valor de 10 ^ 12, entonces excederá el límite de tamaño entero. Procedemos para este problema de otra manera usando tamiz de sundaram y factorización primade un numero Como sabemos, si LCM(a,b) = k, cualquier factor primo de a o b también será el factor primo de ‘k’.
- Tome un factor de array [] de tamaño 10 ^ 6 e inicialícelo con 0 porque los factores primos de cualquier número siempre son menores e iguales a su raíz cuadrada y en nuestra restricción arr [i] <= 10 ^ 12.
- Genere todos los primos menores que e iguales a 10^6 y guárdelos en otra array.
- Ahora, uno por uno, calcule todos los factores primos de cada número en la array y márquelos como 1 en la array factor[].
- Ahora recorra la array factor[] e imprima todos los índices que están marcados como 1 porque estos serán factores primos de mcm de n números en la array dada.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find prime factors of LCM of array elements
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
typedef long long int ll;
// array to store all prime less than and equal to 10^6
vector <int> primes;
// utility function for sieve of sundaram
void sieve()
{
int n = MAX;
// In general Sieve of Sundaram, produces primes smaller
// than (2*x + 2) for a number given number x. Since
// we want primes smaller than n, we reduce n to half
int nNew = (n)/2;
// This array is used to separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
bool marked[nNew + 100];
// Initialize all elements as not marked
memset(marked, false, sizeof(marked));
// Main logic of Sundaram. Mark all numbers which do not
// generate prime number by doing 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;
// Since 2 is a prime number
primes.push_back(2);
// Print other primes. Remaining primes are of the form
// 2*i + 1 such that marked[i] is false.
for (int i=1; i<=nNew; i++)
if (marked[i] == false)
primes.push_back(2*i + 1);
}
// Function to find prime factors of n elements of
// given array
void primeLcm(ll arr[], int n )
{
// factors[] --> array to mark all prime factors of
// lcm of array elements
int factors[MAX] = {0};
// One by one calculate prime factors of number
// and mark them in factors[] array
for (int i=0; i<n; i++)
{
// copy --> duplicate of original element to
// perform operation
ll copy = arr[i];
// sqr --> square root of current number 'copy'
// because all prime factors are always less
// than and equal to square root of given number
int sqr = sqrt(copy);
// check divisibility with prime factor
for (int j=0; primes[j]<=sqr; j++)
{
// if current prime number is factor of 'copy'
if (copy%primes[j] == 0)
{
// divide with current prime factor until
// it can divide the number
while (copy%primes[j] == 0)
copy = copy/primes[j];
// mark current prime factor as 1 in
// factors[] array
factors[primes[j]] = 1;
}
}
// After calculating exponents of all prime factors
// either value of 'copy' will be 1 because of
// complete divisibility or remaining value of
// 'copy' will be surely a prime , so we will
// also mark this prime as a factor
if (copy > 1)
factors[copy] = 1;
}
// if 2 is prime factor of lcm of all elements
// in given array
if (factors[2] == 1)
cout << 2 << " ";
// traverse to print all prime factors of lcm of
// all elements in given array
for (int i=3; i<=MAX; i=i+2)
if (factors[i] == 1)
cout << i << " ";
}
// Driver program to run the case
int main()
{
sieve();
ll arr[] = {20, 10, 15, 60};
int n = sizeof(arr)/sizeof(arr[0]);
primeLcm(arr, n);
return 0;
}
Java
// Java program to find prime
// factors of LCM of array elements
import java.util.*;
class GFG
{
static int MAX = 1000000;
// array to store all prime less
// than and equal to 10^6
static ArrayList<Integer> primes = new ArrayList<Integer>();
// utility function for sieve of sundaram
static void sieve()
{
int n = MAX;
// In general Sieve of Sundaram,
// produces primes smaller than
// (2*x + 2) for a number given
// number x. Since we want primes
// smaller than n, we reduce n to half
int nNew = (n) / 2;
// This array is used to separate
// numbers of the form i+j+2ij
// from others where 1 <= i <= j
boolean[] marked = new boolean[nNew + 100];
// Main logic of Sundaram. Mark all
// numbers which do not generate
// prime number by doing 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;
// Since 2 is a prime number
primes.add(2);
// Print other primes. Remaining
// primes are of the form 2*i + 1
// such that marked[i] is false.
for (int i = 1; i <= nNew; i++)
if (marked[i] == false)
primes.add(2 * i + 1);
}
// Function to find prime factors
// of n elements of given array
static void primeLcm(int[] arr, int n )
{
// factors[] --> array to mark all prime
// factors of lcm of array elements
int[] factors = new int[MAX];
// One by one calculate prime factors of number
// and mark them in factors[] array
for (int i = 0; i < n; i++)
{
// copy --> duplicate of original element to
// perform operation
int copy = arr[i];
// sqr --> square root of current number 'copy'
// because all prime factors are always less
// than and equal to square root of given number
int sqr = (int)Math.sqrt(copy);
// check divisibility with prime factor
for (int j = 0; primes.get(j) <= sqr; j++)
{
// if current prime number is factor of 'copy'
if (copy % primes.get(j) == 0)
{
// divide with current prime factor until
// it can divide the number
while (copy % primes.get(j) == 0)
copy = copy / primes.get(j);
// mark current prime factor as 1 in
// factors[] array
factors[primes.get(j)] = 1;
}
}
// After calculating exponents of all prime factors
// either value of 'copy' will be 1 because of
// complete divisibility or remaining value of
// 'copy' will be surely a prime , so we will
// also mark this prime as a factor
if (copy > 1)
factors[copy] = 1;
}
// if 2 is prime factor of lcm of all elements
// in given array
if (factors[2] == 1)
System.out.print("2 ");
// traverse to print all prime factors of lcm of
// all elements in given array
for (int i = 3; i <= MAX; i = i + 2)
if (factors[i] == 1)
System.out.print(i+" ");
}
// Driver code
public static void main (String[] args)
{
sieve();
int[] arr = {20, 10, 15, 60};
int n = arr.length;
primeLcm(arr, n);
}
}
// This code is contributed by chandan_jnu
Python3
# Python3 program to find prime factors
# of LCM of array elements
import math;
MAX = 10000;
# array to store all prime less than
# and equal to 10^6
primes = [];
# utility function for sieve of sundaram
def sieve():
n = MAX;
# In general Sieve of Sundaram, produces
# primes smaller than (2*x + 2) for a
# number given number x. Since we want
# primes smaller than n, we reduce n to half
nNew = int(n / 2);
# This array is used to separate numbers of
# the form i+j+2ij from others where 1 <= i <= j
marked = [False] * (nNew + 100);
# Main logic of Sundaram. Mark all numbers
# which do not generate prime number by
# doing 2*i+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;
# Since 2 is a prime number
primes.append(2);
# Print other primes. Remaining primes
# are of the form 2*i + 1 such that
# marked[i] is false.
for i in range(1, nNew + 1):
if (marked[i] == False):
primes.append(2 * i + 1);
# Function to find prime factors of
# n elements of given array
def primeLcm(arr, n ):
# factors[] --> array to mark all prime
# factors of lcm of array elements
factors = [0] * (MAX);
# One by one calculate prime factors of
# number and mark them in factors[] array
for i in range(n):
# copy --> duplicate of original
# element to perform operation
copy = arr[i];
# sqr --> square root of current number
# 'copy' because all prime factors are
# always less than and equal to square
# root of given number
sqr = int(math.sqrt(copy));
# check divisibility with prime factor
j = 0;
while (primes[j] <= sqr):
# if current prime number is
# factor of 'copy'
if (copy % primes[j] == 0):
# divide with current prime factor
# until it can divide the number
while (copy % primes[j] == 0):
copy = int(copy / primes[j]);
# mark current prime factor as 1
# in factors[] array
factors[primes[j]] = 1;
j += 1;
# After calculating exponents of all prime
# factors either value of 'copy' will be 1
# because of complete divisibility or
# remaining value of 'copy' will be surely
# a prime, so we will also mark this prime
# as a factor
if (copy > 1):
factors[copy] = 1;
# if 2 is prime factor of lcm of
# all elements in given array
if (factors[2] == 1):
print("2 ", end = "");
# traverse to print all prime factors of
# lcm of all elements in given array
for i in range(3, MAX + 1, 2):
if (factors[i] == 1):
print(i, end = " ");
# Driver Code
sieve();
arr = [20, 10, 15, 60];
n = len(arr);
primeLcm(arr, n);
# This code is contributed by chandan_jnu
C#
// C# program to find prime
// factors of LCM of array elements
using System;
using System.Collections;
class GFG
{
static int MAX = 1000000;
// array to store all prime less
// than and equal to 10^6
static ArrayList primes = new ArrayList();
// utility function for sieve of sundaram
static void sieve()
{
int n = MAX;
// In general Sieve of Sundaram,
// produces primes smaller than
// (2*x + 2) for a number given
// number x. Since we want primes
// smaller than n, we reduce n to half
int nNew = (n) / 2;
// This array is used to separate
// numbers of the form i+j+2ij
// from others where 1 <= i <= j
bool[] marked = new bool[nNew + 100];
// Main logic of Sundaram. Mark all
// numbers which do not generate
// prime number by doing 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;
// Since 2 is a prime number
primes.Add(2);
// Print other primes. Remaining
// primes are of the form 2*i + 1
// such that marked[i] is false.
for (int i = 1; i <= nNew; i++)
if (marked[i] == false)
primes.Add(2 * i + 1);
}
// Function to find prime factors
// of n elements of given array
static void primeLcm(int[] arr, int n )
{
// factors[] --> array to
// mark all prime factors
// of lcm of array elements
int[] factors = new int[MAX];
// One by one calculate prime
// factors of number and mark
// them in factors[] array
for (int i = 0; i < n; i++)
{
// copy --> duplicate of original
// element to perform operation
int copy = arr[i];
// sqr --> square root of current
// number 'copy' because all prime
// factors are always less than and
// equal to square root of given number
int sqr = (int)Math.Sqrt(copy);
// check divisibility with prime factor
for (int j = 0; (int)primes[j] <= sqr; j++)
{
// if current prime number is factor of 'copy'
if (copy % (int)primes[j] == 0)
{
// divide with current prime factor until
// it can divide the number
while (copy % (int)primes[j] == 0)
copy = copy / (int)primes[j];
// mark current prime factor as 1 in
// factors[] array
factors[(int)primes[j]] = 1;
}
}
// After calculating exponents of all prime factors
// either value of 'copy' will be 1 because of
// complete divisibility or remaining value of
// 'copy' will be surely a prime , so we will
// also mark this prime as a factor
if (copy > 1)
factors[copy] = 1;
}
// if 2 is prime factor of lcm of all elements
// in given array
if (factors[2] == 1)
Console.Write("2 ");
// traverse to print all prime factors of lcm of
// all elements in given array
for (int i = 3; i <= MAX; i = i + 2)
if (factors[i] == 1)
Console.Write(i+" ");
}
// Driver code
static void Main()
{
sieve();
int[] arr = {20, 10, 15, 60};
int n = arr.Length;
primeLcm(arr, n);
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP program to find prime factors of
// LCM of array elements
$MAX = 10000;
// array to store all prime less than
// and equal to 10^6
$primes = array();
// utility function for sieve of sundaram
function sieve()
{
global $MAX, $primes;
$n = $MAX;
// In general Sieve of Sundaram, produces
// primes smaller than (2*x + 2) for a number
// given number x. Since we want primes smaller
// than n, we reduce n to half
$nNew = (int)($n / 2);
// This array is used to separate numbers of
// the form i+j+2ij from others where 1 <= i <= j
$marked = array_fill(0, $nNew + 100, false);
// Main logic of Sundaram. Mark all numbers which
// do not generate prime number by doing 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;
// Since 2 is a prime number
array_push($primes, 2);
// Print other primes. Remaining primes are of
// the form 2*i + 1 such that marked[i] is false.
for ($i = 1; $i <= $nNew; $i++)
if ($marked[$i] == false)
array_push($primes, 2 * $i + 1);
}
// Function to find prime factors of n
// elements of given array
function primeLcm($arr, $n )
{
global $MAX, $primes;
// factors[] --> array to mark all prime
// factors of lcm of array elements
$factors = array_fill(0, $MAX, 0);
// One by one calculate prime factors of
// number and mark them in factors[] array
for ($i = 0; $i < $n; $i++)
{
// copy --> duplicate of original
// element to perform operation
$copy = $arr[$i];
// sqr --> square root of current number
// 'copy' because all prime factors are
// always less than and equal to square
// root of given number
$sqr = (int)sqrt($copy);
// check divisibility with prime factor
for ($j = 0; $primes[$j] <= $sqr; $j++)
{
// if current prime number is factor
// of 'copy'
if ($copy % $primes[$j] == 0)
{
// divide with current prime factor
// until it can divide the number
while ($copy % $primes[$j] == 0)
$copy = (int)($copy / $primes[$j]);
// mark current prime factor as 1
// in factors[] array
$factors[$primes[$j]] = 1;
}
}
// After calculating exponents of all prime
// factors either value of 'copy' will be 1
// because of complete divisibility or remaining
// value of 'copy' will be surely a prime , so
// we will also mark this prime as a factor
if ($copy > 1)
$factors[$copy] = 1;
}
// if 2 is prime factor of lcm of all
// elements in given array
if ($factors[2] == 1)
echo "2 ";
// traverse to print all prime factors of
// lcm of all elements in given array
for ($i = 3; $i <= $MAX; $i = $i + 2)
if ($factors[$i] == 1)
echo $i . " ";
}
// Driver Code
sieve();
$arr = array(20, 10, 15, 60);
$n = count($arr);
primeLcm($arr, $n);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// JavaScript program to find prime
// factors of LCM of array elements
let MAX = 1000000;
// array to store all prime less
// than and equal to 10^6
let primes = [];
// utility function for sieve of sundaram
function sieve()
{
let n = MAX;
// In general Sieve of Sundaram,
// produces primes smaller than
// (2*x + 2) for a number given
// number x. Since we want primes
// smaller than n, we reduce n to half
let nNew = parseInt((n) / 2, 10);
// This array is used to separate
// numbers of the form i+j+2ij
// from others where 1 <= i <= j
let marked = new Array(nNew + 100);
marked.fill(false);
// Main logic of Sundaram. Mark all
// numbers which do not generate
// prime number by doing 2*i+1
let tmp = parseInt(Math.sqrt(n), 10);
for (let i = 1; i <= parseInt((tmp - 1) / 2, 10); i++)
for (let j = (i * (i + 1)) << 1; j <= nNew;
j = j + 2 * i + 1)
marked[j] = true;
// Since 2 is a prime number
primes.push(2);
// Print other primes. Remaining
// primes are of the form 2*i + 1
// such that marked[i] is false.
for (let i = 1; i <= nNew; i++)
if (marked[i] == false)
primes.push(2 * i + 1);
}
// Function to find prime factors
// of n elements of given array
function primeLcm(arr, n)
{
// factors[] --> array to
// mark all prime factors
// of lcm of array elements
let factors = new Array(MAX);
// One by one calculate prime
// factors of number and mark
// them in factors[] array
for (let i = 0; i < n; i++)
{
// copy --> duplicate of original
// element to perform operation
let copy = arr[i];
// sqr --> square root of current
// number 'copy' because all prime
// factors are always less than and
// equal to square root of given number
let sqr = parseInt(Math.sqrt(copy), 10);
// check divisibility with prime factor
for (let j = 0; primes[j] <= sqr; j++)
{
// if current prime number is factor of 'copy'
if (copy % primes[j] == 0)
{
// divide with current prime factor until
// it can divide the number
while (copy % primes[j] == 0)
copy = parseInt(copy / primes[j], 10);
// mark current prime factor as 1 in
// factors[] array
factors[primes[j]] = 1;
}
}
// After calculating exponents of all prime factors
// either value of 'copy' will be 1 because of
// complete divisibility or remaining value of
// 'copy' will be surely a prime , so we will
// also mark this prime as a factor
if (copy > 1)
factors[copy] = 1;
}
// if 2 is prime factor of lcm of all elements
// in given array
if (factors[2] == 1)
document.write("2 ");
// traverse to print all prime factors of lcm of
// all elements in given array
for (let i = 3; i <= MAX; i = i + 2)
if (factors[i] == 1)
document.write(i+" ");
}
sieve();
let arr = [20, 10, 15, 60];
let n = arr.length;
primeLcm(arr, n);
</script>
Producción:
2 3 5
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA