Número más pequeño divisible por los primeros n números

Dado un número n , encuentre el número más pequeño divisible por cada número de 1 a n.
Ejemplos: 
 

Input : n = 4
Output : 12
Explanation : 12 is the smallest numbers divisible
              by all numbers from 1 to 4

Input : n = 10
Output : 2520

Input :  n = 20
Output : 232792560

Si observas con atención, la respuesta debe ser el MCM de los números 1 a n . 
Para encontrar MCM de números del 1 al n – 
 

1. Inicializar ans = 1. 
    
2. Iterar sobre todos los números desde i = 1 hasta i = n. 
   En la i-ésima iteración ans = LCM(1, 2, …….., i) . Esto se puede hacer fácilmente como LCM(1, 2, …., i) = LCM(ans, i) . 
   Por lo tanto, en la i-ésima iteración solo tenemos que hacer: 
    

ans = LCM(ans, i) 
         = ans * i / gcd(ans, i) [Using the below property,
                                 a*b = gcd(a,b) * lcm(a,b)]

Nota: en el código C++, la respuesta supera rápidamente el límite de enteros, incluso el límite largo largo.
A continuación se muestra la implementación de la lógica. 
 

// C++ program to find smallest number evenly divisible by
// all numbers 1 to n
#include<bits/stdc++.h>
using namespace std;
 
// Function returns the lcm of first n numbers
long long lcm(long long n)
{
    long long ans = 1;   
    for (long long i = 1; i <= n; i++)
        ans = (ans * i)/(__gcd(ans, i));
    return ans;
}
 
// Driver program to test the above function
int main()
{
    long long n = 20;
    cout << lcm(n);
    return 0;
}

// Java program to find the smallest number evenly divisible by
// all numbers 1 to n
 
 class GFG{
 
static long gcd(long a, long b)
{
   if(a%b != 0)
      return gcd(b,a%b);
   else
      return b;
}
 
// Function returns the lcm of first n numbers
static long lcm(long n)
{
    long ans = 1;   
    for (long i = 1; i <= n; i++)
        ans = (ans * i)/(gcd(ans, i));
    return ans;
}
  
// Driver program to test the above function
public static void main(String []args)
{
    long n = 20;
    System.out.println(lcm(n));
 
}
}

// C#  program to find smallest number
// evenly divisible by
// all numbers 1 to n
using System;
 
public class GFG{
    static long gcd(long a, long b)
{
if(a%b != 0)
    return gcd(b,a%b);
else
    return b;
}
 
// Function returns the lcm of first n numbers
static long lcm(long n)
{
    long ans = 1;    
    for (long i = 1; i <= n; i++)
        ans = (ans * i)/(gcd(ans, i));
    return ans;
}
 
// Driver program to test the above function
    static public void Main (){
        long n = 20;
        Console.WriteLine(lcm(n));
    }
//This code is contributed by akt_mit   
}

# Python program to find the smallest number evenly 
# divisible by all number 1 to n
import math
   
# Returns the lcm of first n numbers
def lcm(n):
    ans = 1
    for i in range(1, n + 1):
        ans = int((ans * i)/math.gcd(ans, i))        
    return ans
   
# main
n = 20
print (lcm(n))

<?php
// Note: This code is not working on GFG-IDE
// because gmp libraries are not supported
 
// PHP program to find smallest number
// evenly divisible by all numbers 1 to n
 
// Function returns the lcm
// of first n numbers
function lcm($n)
{
    $ans = 1;
    for ($i = 1; $i <= $n; $i++)
        $ans = ($ans * $i) / (gmp_gcd(strval(ans),
                                      strval(i)));
    return $ans;
}
 
// Driver Code
$n = 20;
echo lcm($n);
 
// This code is contributed by mits
?>

<script>
 
// Javascript program to find the smallest number evenly divisible by
// all numbers 1 to n
 
function gcd(a, b)
{
   if(a%b != 0)
      return gcd(b,a%b);
   else
      return b;
}
   
// Function returns the lcm of first n numbers
function lcm(n)
{
    let ans = 1;   
    for (let i = 1; i <= n; i++)
        ans = (ans * i)/(gcd(ans, i));
    return ans;
}
       
// function call
     
    let n = 20;
    document.write(lcm(n));
     
</script>

Producción : 

232792560

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. Consulte el artículo a continuación para conocer el enfoque basado en Sieve. 
MCM de Primeros n Números Naturales
Este artículo es una contribución de Ayush Khanduri . 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.