Dado un número n tal que 1 <= N <= 10^6, la tarea es encontrar el MCM de los primeros n números naturales.
Ejemplos:
Input : n = 5 Output : 60 Input : n = 6 Output : 60 Input : n = 7 Output : 420
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Hemos discutido una solución simple en el siguiente artículo.
Número más pequeño divisible por los primeros n números
La solución anterior funciona bien para una sola entrada. Pero si tenemos múltiples entradas, es una buena idea usar la Criba de Eratóstenes para almacenar todos los factores primos. Como sabemos, si MCM(a, b) = X, cualquier factor primo de a o b también será el factor primo de ‘X’.
- Inicialice la variable lcm con 1
- Genere una criba de Eratóstenes (vector bool isPrime) de longitud 10 ^ 6 (idealmente debe ser igual al número de dígitos en factorial)
- Ahora, para cada número en el vector bool isPrime, si el número es primo (isPrime[i] es verdadero), encuentra el número máximo que es menor que el número dado e igual a la potencia del primo.
- Luego multiplica este número con la variable mcm.
- Repite los pasos 3 y 4 hasta que el primo sea menor que el número dado.
Ilustración:
For example, if n = 10 8 will be the first number which is equal to 2^3 then 9 which is equal to 3^2 then 5 which is equal to 5^1 then 7 which is equal to 7^1 Finally, we multiply those numbers 8*9*5*7 = 2520
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find LCM of First N Natural Numbers.
#include <bits/stdc++.h>
#define MAX 100000
using namespace std;
vector<bool> isPrime (MAX, true);
// utility function for sieve of sieve of Eratosthenes
void sieve()
{
for (int i = 2; i * i <= MAX; i++)
{
if (isPrime[i] == true)
for (int j = i*i; j<= MAX; j+=i)
isPrime[j] = false;
}
}
// Function to find LCM of first n Natural Numbers
long long LCM(int n)
{
long long lcm = 1;
int i=2;
while(i<=n) {
if(isPrime[i]){
int pp = i;
while (pp * i <= n)
pp = pp * i;
lcm *= pp;
}
i++;
}
return lcm;
}
// Driver code
int main()
{
// build sieve
sieve();
int N = 7;
// Function call
cout << LCM(N);
return 0;
}
Java
// Java program to find LCM of First N Natural Numbers.
import java.util.*;
class GFG
{
static int MAX = 100000;
// array to store all prime less than and equal to 10^6
static ArrayList<Integer> primes
= new ArrayList<Integer>();
// utility function for sieve of sieve of Eratosthenes
static void sieve()
{
boolean[] isComposite = new boolean[MAX + 1];
for (int i = 2; i * i <= MAX; i++)
{
if (isComposite[i] == false)
for (int j = 2; j * i <= MAX; j++)
isComposite[i * j] = true;
}
// Store all prime numbers in vector primes[]
for (int i = 2; i <= MAX; i++)
if (isComposite[i] == false)
primes.add(i);
}
// Function to find LCM of first n Natural Numbers
static long LCM(int n)
{
long lcm = 1;
for (int i = 0;
i < primes.size() && primes.get(i) <= n;
i++)
{
// Find the highest power of prime, primes[i]
// that is less than or equal to n
int pp = primes.get(i);
while (pp * primes.get(i) <= n)
pp = pp * primes.get(i);
// multiply lcm with highest power of prime[i]
lcm *= pp;
lcm %= 1000000007;
}
return lcm;
}
// Driver code
public static void main(String[] args)
{
sieve();
int N = 7;
// Function call
System.out.println(LCM(N));
}
}
// This code is contributed by mits
Python3
# Python3 program to find LCM of # First N Natural Numbers. MAX = 100000 # array to store all prime less # than and equal to 10^6 primes = [] # utility function for # sieve of Eratosthenes def sieve(): isComposite = [False]*(MAX+1) i = 2 while (i * i <= MAX): if (isComposite[i] == False): j = 2 while (j * i <= MAX): isComposite[i * j] = True j += 1 i += 1 # Store all prime numbers in # vector primes[] for i in range(2, MAX+1): if (isComposite[i] == False): primes.append(i) # Function to find LCM of # first n Natural Numbers def LCM(n): lcm = 1 i = 0 while (i < len(primes) and primes[i] <= n): # Find the highest power of prime, # primes[i] that is less than or # equal to n pp = primes[i] while (pp * primes[i] <= n): pp = pp * primes[i] # multiply lcm with highest # power of prime[i] lcm *= pp lcm %= 1000000007 i += 1 return lcm # Driver code sieve() N = 7 # Function call print(LCM(N)) # This code is contributed by mits
C#
// C# program to find LCM of First N
// Natural Numbers.
using System.Collections;
using System;
class GFG {
static int MAX = 100000;
// array to store all prime less than
// and equal to 10^6
static ArrayList primes = new ArrayList();
// utility function for sieve of
// sieve of Eratosthenes
static void sieve()
{
bool[] isComposite = new bool[MAX + 1];
for (int i = 2; i * i <= MAX; i++)
{
if (isComposite[i] == false)
for (int j = 2; j * i <= MAX; j++)
isComposite[i * j] = true;
}
// Store all prime numbers in vector primes[]
for (int i = 2; i <= MAX; i++)
if (isComposite[i] == false)
primes.Add(i);
}
// Function to find LCM of first
// n Natural Numbers
static long LCM(int n)
{
long lcm = 1;
for (int i = 0;
i < primes.Count && (int)primes[i] <= n;
i++)
{
// Find the highest power of prime, primes[i]
// that is less than or equal to n
int pp = (int)primes[i];
while (pp * (int)primes[i] <= n)
pp = pp * (int)primes[i];
// multiply lcm with highest power of prime[i]
lcm *= pp;
lcm %= 1000000007;
}
return lcm;
}
// Driver code
public static void Main()
{
sieve();
int N = 7;
// Function call
Console.WriteLine(LCM(N));
}
}
// This code is contributed by mits
Javascript
<script>
// Javascript program to find LCM of First N
// Natural Numbers.
let MAX = 100000;
// array to store all prime less than
// and equal to 10^6
let primes = [];
// utility function for sieve of
// sieve of Eratosthenes
function sieve()
{
let isComposite = new Array(MAX + 1);
isComposite.fill(false);
for (let i = 2; i * i <= MAX; i++)
{
if (isComposite[i] == false)
for (let j = 2; j * i <= MAX; j++)
isComposite[i * j] = true;
}
// Store all prime numbers in vector primes[]
for (let i = 2; i <= MAX; i++)
if (isComposite[i] == false)
primes.push(i);
}
// Function to find LCM of first
// n Natural Numbers
function LCM(n)
{
let lcm = 1;
for (let i = 0;
i < primes.length && primes[i] <= n;
i++)
{
// Find the highest power of prime, primes[i]
// that is less than or equal to n
let pp = primes[i];
while (pp * primes[i] <= n)
pp = pp * primes[i];
// multiply lcm with highest power of prime[i]
lcm *= pp;
lcm %= 1000000007;
}
return lcm;
}
sieve();
let N = 7;
// Function call
document.write(LCM(N));
// This code is contributed by decode2207.
</script>
PHP
<?php
// PHP program to find LCM of
// First N Natural Numbers.
$MAX = 100000;
// array to store all prime less
// than and equal to 10^6
$primes = array();
// utility function for
// sieve of Eratosthenes
function sieve()
{
global $MAX, $primes;
$isComposite = array_fill(0, $MAX, false);
for ($i = 2; $i * $i <= $MAX; $i++)
{
if ($isComposite[$i] == false)
for ($j = 2; $j * $i <= $MAX; $j++)
$isComposite[$i * $j] = true;
}
// Store all prime numbers in
// vector primes[]
for ($i = 2; $i <= $MAX; $i++)
if ($isComposite[$i] == false)
array_push($primes, $i);
}
// Function to find LCM of
// first n Natural Numbers
function LCM($n)
{
global $MAX, $primes;
$lcm = 1;
for ($i = 0; $i < count($primes) &&
$primes[$i] <= $n; $i++)
{
// Find the highest power of prime,
// primes[i] that is less than or
// equal to n
$pp = $primes[$i];
while ($pp * $primes[$i] <= $n)
$pp = $pp * $primes[$i];
// multiply lcm with highest
// power of prime[i]
$lcm *= $pp;
$lcm %= 1000000007;
}
return $lcm;
}
// Driver code
sieve();
$N = 7;
// Function call
echo LCM($N);
// This code is contributed by mits
?>
Producción
420
Complejidad de Tiempo : O(n 2 )
Espacio Auxiliar: O(n)
Otro enfoque:
La idea es que si el número es menor que 3, devuelva el número. Si el número es mayor que 2, encuentra el MCM de n,n-1
- Digamos x=MCM(n,n-1)
- de nuevo x=mcm(x,n-2)
- de nuevo x=MCM(x,n-3) …
- .
- .
- de nuevo x=mcm(x,1)…
ahora el resultado es x.
Para encontrar LCM(a,b) usamos una función hcf(a,b) que devolverá HCF de (a,b)
Sabemos que MCM(a,b)= (a*b)/HCF(a,b)
Ilustración:
For example, if n = 7 function call lcm(7,6) now lets say a=7 , b=6 Now , b!= 1 Hence a=lcm(7,6) = 42 and b=6-1=5 function call lcm(42,5) a=lcm(42,5) = 210 and b=5-1=4 function call lcm(210,4) a=lcm(210,4) = 420 and b=4-1=3 function call lcm(420,3) a=lcm(420,3) = 420 and b=3-1=2 function call lcm(420,2) a=lcm(420,2) = 420 and b=2-1=1 Now b=1 Hence return a=420
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find LCM of First N Natural Numbers.
#include <bits/stdc++.h>
using namespace std;
// to calculate hcf
int hcf(int a, int b)
{
if (b == 0)
return a;
return hcf(b, a % b);
}
int findlcm(int a,int b)
{
if (b == 1)
// lcm(a,b)=(a*b)/hcf(a,b)
return a;
// assign a=lcm of n,n-1
a = (a * b) / hcf(a, b);
// b=b-1
b -= 1;
return findlcm(a, b);
}
// Driver code
int main()
{
int n = 7;
if (n < 3)
cout << n; // base case
else
// Function call
// pass n,n-1 in function to find LCM of first n natural
// number
cout << findlcm(n, n - 1);
return 0;
}
// contributed by ajaykr00kj
Java
// Java program to find LCM of First N Natural Numbers
public class Main
{
// to calculate hcf
static int hcf(int a, int b)
{
if (b == 0)
return a;
return hcf(b, a % b);
}
static int findlcm(int a,int b)
{
if (b == 1)
// lcm(a,b)=(a*b)/hcf(a,b)
return a;
// assign a=lcm of n,n-1
a = (a * b) / hcf(a, b);
// b=b-1
b -= 1;
return findlcm(a, b);
}
// Driver code.
public static void main(String[] args)
{
int n = 7;
if (n < 3)
System.out.print(n); // base case
else
// Function call
// pass n,n-1 in function to find LCM of first n natural
// number
System.out.print(findlcm(n, n - 1));
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python3 program to find LCM # of First N Natural Numbers. # To calculate hcf def hcf(a, b): if (b == 0): return a return hcf(b, a % b) def findlcm(a, b): if (b == 1): # lcm(a,b)=(a*b)//hcf(a,b) return a # Assign a=lcm of n,n-1 a = (a * b) // hcf(a, b) # b=b-1 b -= 1 return findlcm(a, b) # Driver code n = 7 if (n < 3): print(n) else: # Function call # pass n,n-1 in function # to find LCM of first n # natural number print(findlcm(n, n - 1)) # This code is contributed by Shubham_Singh
C#
// C# program to find LCM of First N Natural Numbers.
using System;
class GFG {
// to calculate hcf
static int hcf(int a, int b)
{
if (b == 0)
return a;
return hcf(b, a % b);
}
static int findlcm(int a,int b)
{
if (b == 1)
// lcm(a,b)=(a*b)/hcf(a,b)
return a;
// assign a=lcm of n,n-1
a = (a * b) / hcf(a, b);
// b=b-1
b -= 1;
return findlcm(a, b);
}
// Driver code
static void Main() {
int n = 7;
if (n < 3)
Console.Write(n); // base case
else
// Function call
// pass n,n-1 in function to find LCM of first n natural
// number
Console.Write(findlcm(n, n - 1));
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program to find LCM of First N Natural Numbers.
// to calculate hcf
function hcf(a, b)
{
if (b == 0)
return a;
return hcf(b, a % b);
}
function findlcm(a,b)
{
if (b == 1)
// lcm(a,b)=(a*b)/hcf(a,b)
return a;
// assign a=lcm of n,n-1
a = (a * b) / hcf(a, b);
// b=b-1
b -= 1;
return findlcm(a, b);
}
let n = 7;
if (n < 3)
document.write(n); // base case
else
// Function call
// pass n,n-1 in function to find LCM of first n natural
// number
document.write(findlcm(n, n - 1));
</script>
Producción
420
Complejidad temporal: O(nlog n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Kuldeep Singh (kulli_d_coder) . 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