Smallest Number Divisible by First n Numbers

Have you ever wondered what is the smallest number that can be evenly divided by all the numbers from 1 up to a given number (n)? This problem has applications in various areas of mathematics and computer science, such as number theory and algorithm design. In this blog, we'll explore different approaches to solve this problem, understand the underlying concepts, and see some practical examples.

Table of Content#

  1. Problem Statement
  2. Brute - Force Approach
    • How it works
    • Limitations
  3. Prime Factorization Approach
    • Prime Factorization Basics
    • Algorithm Steps
    • Example
  4. Using the Least Common Multiple (LCM) Property
    • LCM Definition
    • LCM of Multiple Numbers
    • Algorithm using LCM
  5. Best Practices and Optimizations
    • Time Complexity Analysis
    • Space Complexity Analysis
    • Optimizing for Large (n)
  6. Example Usage in Programming
    • Python Code Example
    • Java Code Example
  7. References

1. Problem Statement#

Given a positive integer (n), find the smallest positive integer (x) such that (x) is divisible by all integers from (1) to (n). For example, if (n = 3), the numbers are (1), (2), and (3). The smallest number divisible by all of them is (6).

2. Brute - Force Approach#

How it works#

The brute - force approach is straightforward. We start with a candidate number (x = n) and keep incrementing (x) by (1) until we find a number that is divisible by all numbers from (1) to (n).

Limitations#

  • Time Complexity: For a given (n), in the worst - case scenario, we may have to check (O(n^2)) numbers. For example, if (n) is large (say (n = 100)), this approach becomes extremely slow.
  • Inefficiency: It doesn't take advantage of any mathematical properties of numbers.

3. Prime Factorization Approach#

Prime Factorization Basics#

Prime factorization of a number (m) is expressing (m) as a product of prime numbers. For example, (12=2^2\times3^1).

Algorithm Steps#

  1. Find Prime Factors: For each number (i) from (2) to (n), find its prime factorization.
  2. Track Maximum Exponents: For each prime number (p), track the maximum exponent (e) such that (p^e) divides some number from (1) to (n).
  3. Compute the Result: Multiply all (p^e) together.

Example#

Let (n = 4).

  • Prime factorization of (2=2^1)
  • Prime factorization of (3 = 3^1)
  • Prime factorization of (4=2^2)

For prime (2), the maximum exponent is (2). For prime (3), the maximum exponent is (1). The result is (2^2\times3^1=12).

4. Using the Least Common Multiple (LCM) Property#

LCM Definition#

The least common multiple of two numbers (a) and (b), denoted as (LCM(a,b)), is the smallest positive integer that is divisible by both (a) and (b). It can be calculated using the formula (LCM(a,b)=\frac{a\times b}{GCD(a,b)}), where (GCD) is the greatest common divisor.

LCM of Multiple Numbers#

The LCM of (n) numbers (a_1,a_2,\cdots,a_n) can be calculated as (LCM(a_1,LCM(a_2,\cdots,LCM(a_{n - 1},a_n))))

Algorithm using LCM#

We can calculate the LCM of numbers from (1) to (n) iteratively. Start with (lcm = 1), and for each (i) from (2) to (n), update (lcm) as (lcm=\frac{lcm\times i}{GCD(lcm,i)})

5. Best Practices and Optimizations#

Time Complexity Analysis#

  • Prime Factorization Approach:
    • Finding prime factors for each number from (2) to (n) can be done in (O(n\sqrt{n})) time (using trial division for prime factorization). But with more efficient prime factorization algorithms (like Sieve of Eratosthenes for pre - computing primes), it can be optimized.
  • LCM Approach:
    • Calculating (GCD) using the Euclidean algorithm takes (O(\log a+\log b)) time. For (n) numbers, the time complexity is (O(n\log n)) (assuming (GCD) calculations are efficient).

Space Complexity Analysis#

  • Prime Factorization Approach: Requires space to store prime factors, which is (O(n)) in the worst - case (if all numbers from (2) to (n) are prime).
  • LCM Approach: Requires (O(1)) additional space (except for storing the result).

Optimizing for Large (n)#

  • Pre - compute Primes: Use the Sieve of Eratosthenes to pre - compute prime numbers up to (n) for faster prime factorization.
  • Efficient GCD Calculation: Implement the Euclidean algorithm efficiently (recursive or iterative).

6. Example Usage in Programming#

Python Code Example#

import math
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
 
def smallest_divisible(n):
    result = 1
    for i in range(2, n + 1):
        result = (result * i) // gcd(result, i)
    return result
 
 
n = 10
print(smallest_divisible(n))

Java Code Example#

public class SmallestDivisible {
    static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
 
    static int smallestDivisible(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result = (result * i) / gcd(result, i);
        }
        return result;
    }
 
    public static void main(String[] args) {
        int n = 10;
        System.out.println(smallestDivisible(n));
    }
}

7. References#

  • "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
  • Online resources on number theory and algorithm design (e.g., GeeksforGeeks, HackerRank documentation).

This blog has covered different aspects of finding the smallest number divisible by the first (n) numbers. Whether you choose the prime factorization approach or the LCM - based approach, understanding the mathematical concepts and optimizing the algorithms are key to solving this problem efficiently.

2026-07