Find Prime Factorisation of a Number using Sieve

Problem Statement❯

Given a number n, your task is to find its prime factorization using the Sieve of Eratosthenes approach. This method is efficient when you need to factorize multiple numbers quickly.

The idea is to first precompute the smallest prime factor (SPF) for every number up to a certain limit using a modified sieve, and then use that information to efficiently extract the prime factors of any number up to that limit.

Examples❯

n	Output	Description
60	[2, 2, 3, 5]	60 = 2 × 2 × 3 × 5; factors extracted using smallest prime factor sieve
97	[97]	97 is a prime number; only one factor which is itself
1	[]	1 has no prime factors; factorization returns empty list
100	[2, 2, 5, 5]	100 = 2² × 5²; SPF quickly gives repeated prime divisors
2	[2]	2 is the smallest prime number; factor is [2]
0	[]	0 has no valid prime factorization; returns empty list
""	[]	Empty input is treated as invalid or 0; returns empty list
360	[2, 2, 2, 3, 3, 5]	360 = 2³ × 3² × 5; SPF gives factors in order
999983	[999983]	A large prime number; only factor is itself
1024	[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]	1024 = 2¹⁰; all prime factors are 2

Solution❯

Understanding the Problem

We are given a number n, and our task is to find its prime factorization — that is, express it as a product of prime numbers.

To do this efficiently, especially when we have to factorize many numbers, we can use a technique based on the Sieve of Eratosthenes. Instead of just marking prime numbers, we compute the Smallest Prime Factor (SPF) for every number up to a certain limit.

Once we have this SPF array, we can use it to find the prime factors of any number ≤ limit quickly by continuously dividing the number by its SPF until it becomes 1.

Step-by-Step Solution with Example

step 1: Precompute the Smallest Prime Factor (SPF)

We initialize an array spf[] such that spf[i] = i initially.

We iterate from 2 to limit and if i is a prime (i.e., spf[i] == i), then for every multiple j of i, we set spf[j] = i only if spf[j] == j. This ensures that each number gets its smallest prime divisor.

step 2: Use SPF to Factorize the Number

Let’s say we want to factorize n = 60. We use the spf[] array and do the following:

Start with n = 60
spf[60] = 2 ⇒ store 2, then divide: n = 60 / 2 = 30
spf[30] = 2 ⇒ store 2, then divide: n = 30 / 2 = 15
spf[15] = 3 ⇒ store 3, then divide: n = 15 / 3 = 5
spf[5] = 5 ⇒ store 5, then divide: n = 5 / 5 = 1

We stop when n becomes 1. So, the prime factorization of 60 is: 2, 2, 3, 5

step 3: Output the Result

We now have a list of prime factors that can be printed or returned as needed.

Edge Cases

n = 1: No prime factors, since 1 is neither prime nor composite. Return an empty list.
n is a prime: For example, n = 13 → spf[13] = 13 → 13 is its only prime factor.
Repeated prime factors: Like 2 × 2 × 2 × 2 for n = 16. The algorithm handles this naturally as we keep dividing by the SPF until n becomes 1.
Multiple queries: This approach is especially useful if we need to factorize multiple numbers, as SPF is computed once and reused.

Final Thoughts

This method is highly efficient for prime factorization when dealing with many queries. The preprocessing with the sieve takes O(n log log n), and each factorization takes O(log n) time due to repeated divisions by primes.

By understanding and visualizing each step, especially through the example of n = 60, beginners can grasp how the sieve helps break down numbers into primes quickly and systematically.

Algorithm Steps❯

Precompute the smallest prime factor (SPF) for all numbers up to a maximum limit using a modified Sieve of Eratosthenes.
To factorize a number n, repeatedly divide it by its smallest prime factor (from the spf array) and store each factor.
Continue the process until n becomes 1.
The stored factors will be the prime factors of the number.

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 1000000

int spf[MAX + 1]; // smallest prime factor array

void sieve() {
    for (int i = 1; i <= MAX; i++) spf[i] = i;
    spf[1] = 1;
    for (int i = 2; i * i <= MAX; i++) {
        if (spf[i] == i) { // i is prime
            for (int j = i * i; j <= MAX; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}

void primeFactorization(int n) {
    printf("Prime factors of %d: ", n);
    while (n > 1) {
        printf("%d ", spf[n]);
        n /= spf[n];
    }
    printf("\n");
}

int main() {
    sieve();
    int number = 999983; // example input
    primeFactorization(number);
    return 0;
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(log n)	Once the SPF (Smallest Prime Factor) array is precomputed, the factorization of any single number n takes O(log n) time in the best case — when n has large prime factors or fewer distinct factors.
Average Case	O(log n)	On average, a number n has about log n prime factors. Using the SPF array, we can find and divide by these prime factors efficiently, resulting in O(log n) time complexity for factorization.
Worst Case	O(log n)	In the worst case, such as when n is a power of 2 or has many repeated prime factors, each division by the smallest prime factor still reduces n multiplicatively, so the number of steps is bounded by O(log n).

Space Complexity❯

O(N)

Explanation: We need to store the SPF (Smallest Prime Factor) array for all numbers up to N in order to support fast factorization queries. The space requirement is linear with respect to the sieve limit.