Smallest number divisible by first n numbers

Try it on GfG Practice

Given a number n find the smallest number evenly divisible by each number 1 to n.
Examples: 
 

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

If you observe carefully the ans must be the LCM of the numbers 1 to n. 
To find LCM of numbers from 1 to n - 
 

1. Initialize ans = 1. 
    
2. Iterate over all the numbers from i = 1 to i = n. 
   At the i'th iteration ans = LCM(1, 2, …….., i). This can be done easily as LCM(1, 2, …., i) = LCM(ans, i). 
   Thus at i’th iteration we just have to do - 
    

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

Note : In C++ code, the answer quickly exceeds the integer limit, even the long long limit.
Below is the implementation of the logic. 
 

// 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));

}
}

# 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)) 

// 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    
}

// 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;
    console.log(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
?>

232792560

Time Complexity: O(n log2n) as the complexity of _gcd(a,b) in c++ is log2n  and that is running n times in a loop.
Auxiliary Space: O(1)
The above solution works fine for a single input. But if we have multiple inputs, it is a good idea to use Sieve of Eratosthenes to store all prime factors. Please refer below article for Sieve based approach. 

Approach : [Using Sieve of Eratosthenes]

To solve the problem of finding the smallest number divisible by the first 'n' numbers in a more efficient way, we can use the Sieve of Eratosthenes to precompute the prime numbers up to 'n'. Then, we can use these primes to compute the least common multiple (LCM) more efficiently by considering the highest powers of each prime that are less than or equal to 'n'.

Step-by-Step Approach :

• Generate Prime Numbers up to n: Use the Sieve of Eratosthenes to find all prime numbers up to 'n'.
• Compute the LCM using these Primes: For each prime, determine the highest power of that prime which is less than or equal to 'n'. Multiply these highest powers together to get the LCM

Below is the implementation of above approach :

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

// Function to generate all prime numbers up to n using the
// Sieve of Eratosthenes
vector<int> sieve_of_eratosthenes(int n)
{
    vector<bool> is_prime(n + 1, true);
    int p = 2;
    while (p * p <= n) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                is_prime[i] = false;
            }
        }
        ++p;
    }
    vector<int> prime_numbers;
    for (int p = 2; p <= n; ++p) {
        if (is_prime[p]) {
            prime_numbers.push_back(p);
        }
    }
    return prime_numbers;
}

// Function to find the smallest number divisible by all
// numbers from 1 to n
long long smallest_multiple(int n)
{
    vector<int> primes = sieve_of_eratosthenes(n);
    long long lcm = 1;
    for (int prime : primes) {
        // Calculate the highest power of the prime that is
        // <= n
        int power = 1;
        while (pow(prime, power + 1) <= n) {
            ++power;
        }
        lcm *= pow(prime, power);
    }
    return lcm;
}

int main()
{
    int n = 20;
    cout << smallest_multiple(n) <<endl;
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class SmallestMultiple {

    // Function to generate all prime numbers up to n using
    // the Sieve of Eratosthenes
    public static List<Integer> sieveOfEratosthenes(int n)
    {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 0; i <= n; i++) {
            isPrime[i] = true;
        }
        int p = 2;
        while (p * p <= n) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
            p++;
        }
        List<Integer> primeNumbers = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primeNumbers.add(i);
            }
        }
        return primeNumbers;
    }

    // Function to find the smallest number divisible by all
    // numbers from 1 to n
    public static long smallestMultiple(int n)
    {
        List<Integer> primes = sieveOfEratosthenes(n);
        long lcm = 1;
        for (int prime : primes) {
            // Calculate the highest power of the prime that
            // is <= n
            int power = 1;
            while (Math.pow(prime, power + 1) <= n) {
                power++;
            }
            lcm *= Math.pow(prime, power);
        }
        return lcm;
    }

    public static void main(String[] args)
    {
        int n = 20;
        System.out.println(smallestMultiple(n));
    }
}

import math


def sieve_of_eratosthenes(n):
    """Generate all prime numbers up to n."""
    is_prime = [True] * (n + 1)
    p = 2
    while (p * p <= n):
        if (is_prime[p] == True):
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    prime_numbers = [p for p in range(2, n + 1) if is_prime[p]]
    return prime_numbers


def smallest_multiple(n):
    """Find the smallest number divisible by all numbers from 1 to n."""
    primes = sieve_of_eratosthenes(n)
    lcm = 1
    for prime in primes:
        # Calculate the highest power of the prime that is <= n
        power = 1
        while prime ** (power + 1) <= n:
            power += 1
        lcm *= prime ** power
    return lcm


# Example usage:
n = 20
print(smallest_multiple(n))

// Function to generate all prime numbers up to n using the
// Sieve of Eratosthenes
function sieveOfEratosthenes(n)
{
    let isPrime = new Array(n + 1).fill(true);
    let p = 2;
    while (p * p <= n) {
        if (isPrime[p]) {
            for (let i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
        p++;
    }
    let primeNumbers = [];
    for (let p = 2; p <= n; p++) {
        if (isPrime[p]) {
            primeNumbers.push(p);
        }
    }
    return primeNumbers;
}

// Function to find the smallest number divisible by all
// numbers from 1 to n
function smallestMultiple(n)
{
    let primes = sieveOfEratosthenes(n);
    let lcm = 1;
    for (let prime of primes) {
        // Calculate the highest power of the prime that is
        // <= n
        let power = 1;
        while (Math.pow(prime, power + 1) <= n) {
            power++;
        }
        lcm *= Math.pow(prime, power);
    }
    return lcm;
}

// Example usage:
let n = 20;
console.log(smallestMultiple(n));

The smallest number divisible by all numbers from 1 to 20 is 232792560

Time Complexity: O(nloglogn)
Auxiliary Space: O(n)