Smallest number with all numbers from 1 to N as multiples

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Reading time: 30 minutes

In this problem, we will find the smallest number that is perfectly divisible (with remainder 0) by all numbers from 1 to N. We will demonstrate 3 approaches to solve this:

Brute force O(N^3 * log N)
Using prime factorization O(N * log N * log N)
Using insights into the problem O(N * log log N)

Example to understand the problem better: Consider N = 3, then we need to find a number that is perfectly divisible by 1, 2 and 3. Such numbers are:

6, 12, 18, ...

and the smallest number is 6.

You will notice that 6 is a multiple of 1, 2 and 3 but this is not true for all N like N = 4.

For N=4, the smallest such number will be 12 which the multiplication of all numbers result in 24.

We will solve this problem with some great insights.

With this, you will be able to solve Problem 5 of Project Euler.

Brute force approach O(N^3 * log N)

The brute force approach is to check all numbers until we find a number that is divisible by all numbers from 1 to N.

Now, we can figure out that the solution should be >= N as it should be divisible by N. The maximum number as a solution should be N! which is a simple multiplication of all numbers from 1 to N.

N! as be considered as O(N^2). For each number, we have to divide by all numbers from 1 to N to check if it is a solution. This process will take O(N logN) for each number.

Thus, the overall time complexity of this problem will be O(N^3 * logN).

Pseudocode:

int N_factorial = factorial(N);
for(int i = N; i<N_factorial; i++)
    for(int j=1; j <=N; j++)
    {
        if(i%j != 0)
            break;
        if(j == N)
            return i;
     }
return 0;

Implementation:

import java.util.*;              
public class opengenus
{
    static int factorial(int N)
    {
        int solution = 1;
        for(int i=1; i<=N; i++)
            solution *= i;
        return solution;
    }
    static int smallest_number(int N)
    {
        int N_factorial = factorial(N);
        for(int i=1; i<=N_factorial; i++)
        {
            for(int j=1; j<=N; j++)
            {
                if(i%j != 0)
                    break;
                if(j == N)
                    return i;
            }
        }
        return 0;
    }
	public static void main(String [] args)
	{
		int N = 10;
		int answer = smallest_number(N);
		System.out.println(answer);
	}
}

Output:

Improved solution O(N * log N * log N)

To understand the basic idea behind this solution, let us analyze the problem at hand deeper. For a given number A, we have the prime factoriazation as:

A = (p_1 ^ j_1) * (p_2 ^ j_2) * ... * (p_m ^ j_m)

Consider this for all numbers from 1 to N.

Let for a given prime number p_i, each number from 1 to N will have different powers of it within it say (pw_1, pw_2, ... , pw_n).

For our solution S, we need to have as much power of p_i such that it is divisible by all numbers from 1 to N. For this to be possible, we shall take the maximum number from the power set (pw_1, pw_2, ... , pw_n).

We have to do this for all prime factors or prime numbers less that N.

Once we have the maximum power of each prime number, we shall just multiple the prime numbers to the given power to get to our answer.

Generating all primes can be done through a sieve algorithm and it will take O(N log log N) time. There are O(log N) prime numbers less than N and it can take O(log N * log N) time to calculate the prime factoriazation provided multiplication takes O(log N) time. For each prime number, we can maintain only the largest power and we need to go through all N numbers which will take O(N * log N * log N) to get to our solution.

The time complexity of this approach will be O(N * log N * log N).

Implementation:

import java.util.*;              
public class opengenus
{
    static boolean prime[];
    static int prime_num[];
    
	static int sieve (int n) 
	{
	    int a=2;
		for(int i=a; i<=n; i++)
		{         
			prime[i] = true;
		}
		for(int i=a ; i*i<=n ; i++)
		{           
			if(prime[i] == true)
			{
				for(int j=i*2 ; j<=n ; j=j+i)
				{  
					prime[j] = false;
				}
			}
		}
		// move primes to front
		int pos = 0, pos_t = 0;
		for(int i=0; i <= n; i++)
		{
		    if(prime[i] != false)
    		    pos++;
		}
		prime_num = new int[pos];
		for(int i=2; i <= n; i++)
		{
		    if(prime[i] != false)
    		    prime_num[pos_t++] = i;
		}
		return pos; // number of primes
	}
	static int smallest_number(int N)
	{
	    prime = new boolean [N+1];
	    int number = sieve(N);
	    int smallest_number = 1;
	    int factor[] = new int[number];
	    for(int j=2; j<=N; j++)
	    {
	        int j_temp = j;
    	    for(int i=0; i<number; i++)
    	    {
    	        int count = 0;
    	        while(j_temp % prime_num[i] == 0 && j_temp > 0)
    	        {
    	            j_temp = j_temp / prime_num[i];
    	            count++;
    	        }
    	        if(count > factor[i])
    	            factor[i] = count;
    	    }
	    }
	    for(int i=0; i < number; i++)
	    {
	        smallest_number *= (int)(Math.pow(prime_num[i], factor[i]));
	    }
	    return smallest_number;
	}
	public static void main(String [] args)
	{
		int N = 10;
		int answer = smallest_number(N);
		System.out.println(answer);
	}
}

Output:

Efficient solution O(N * log log N)

The most efficient solution is to generate all primes less than N and find the maximum power of the prime which is within N and multiple all such prime powers to get the smallest number.

For example, there are M primes less than N.

p1, p2, ... , pm

With this, for each prime p_i, we need to find the maximum power w_i such that:

p_i ^ w_i <= N

The logic in this case is that w_i is the maximum power that can be associated with p_i prime in prime factorization of any number less than or equal to N.

We can find the maximum power as:

w_i = FLOOR( log(N) / log(p_i) )

where FLOOR takes the largest integer not greater than the input which can be decimal.

Once we find the power for all such primes, we just need to multiple them to get the smallest number such as:

(p_1 ^ w_1) * (p_2 ^ w_2) * ... * (p_m ^ w_m)

This is the smallest number which we need. The process of finding the prime numbers can be done using a sieve algorithm which will take O(N loglog N) in general.

There will be logN primes in general and finding the power for each will take around O(logN) time if assumed not constant.

With this, the time complexity of this approach will be O(N loglogN).

Pseudocode:

primes[] = find_primes(N)
smallest_number = 1
for i = 0 to length(primes)
    p_i = primes[i]
    power = floor(log(N) / log(p_i))
    smallest_number *= (p_i ^ power)
answer = smallest_number

Implementation:

import java.util.*;              
public class opengenus
{
    static boolean prime[];
    static int prime_num[];
    
	static int sieve (int n) 
	{
	    int a=2;
		for(int i=a; i<=n; i++)
		{         
			prime[i] = true;
		}
		for(int i=a ; i*i<=n ; i++)
		{           
			if(prime[i] == true)
			{
				for(int j=i*2 ; j<=n ; j=j+i)
				{  
					prime[j] = false;
				}
			}
		}
		// move primes to front
		int pos = 0, pos_t = 0;
		for(int i=0; i <= n; i++)
		{
		    if(prime[i] != false)
    		    pos++;
		}
		prime_num = new int[pos];
		for(int i=0; i <= n; i++)
		{
		    if(prime[i] != false)
    		    prime_num[pos_t++] = i;
		}
		return pos; // number of primes
	}
	static int smallest_number(int N)
	{
	    prime = new boolean [N+1];
	    int number = sieve(N);
	    int smallest_number = 1;
	    for(int i=0; i<number; i++)
	    {
	        int power = (int)Math.floor(Math.log(N) * 1.0 / Math.log(prime_num[i]));
	        smallest_number *= Math.pow(prime_num[i], power);
	    }
	    return smallest_number;
	}
	public static void main(String [] args)
	{
		int N = 10;
		int answer = smallest_number(N);
		System.out.println(answer);
	}
}

Output: