Find Prime Factorisation of a Number using Sieve

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.

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.

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

#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;
}

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

const int MAX = 1000000;
int spf[MAX + 1];

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) {
            for (int j = i * i; j <= MAX; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }
}

void primeFactorization(int n) {
    cout << "Prime factors of " << n << ": ";
    while (n > 1) {
        cout << spf[n] << " ";
        n /= spf[n];
    }
    cout << endl;
}

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

MAX = 10**6
spf = [0] * (MAX + 1)

def sieve():
    for i in range(MAX + 1):
        spf[i] = i
    spf[1] = 1
    i = 2
    while i * i <= MAX:
        if spf[i] == i:
            for j in range(i * i, MAX + 1, i):
                if spf[j] == j:
                    spf[j] = i
        i += 1

def prime_factorization(n):
    factors = []
    while n > 1:
        factors.append(spf[n])
        n //= spf[n]
    return factors

if __name__ == "__main__":
    sieve()
    number = 999983  # example input
    print("Prime factors of", number, ":", *prime_factorization(number))

public class PrimeFactorization {
    static final int MAX = 1000000;
    static int[] spf = new int[MAX + 1];

    static 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) {
                for (int j = i * i; j <= MAX; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }
    }

    static void primeFactorization(int n) {
        System.out.print("Prime factors of " + n + ": ");
        while (n > 1) {
            System.out.print(spf[n] + " ");
            n /= spf[n];
        }
        System.out.println();
    }

    public static void main(String[] args) {
        sieve();
        int number = 999983; // example input
        primeFactorization(number);
    }
}

const MAX = 1000000;
const spf = new Array(MAX + 1);

function sieve() {
  for (let i = 1; i <= MAX; i++) spf[i] = i;
  spf[1] = 1;
  for (let i = 2; i * i <= MAX; i++) {
    if (spf[i] === i) {
      for (let j = i * i; j <= MAX; j += i) {
        if (spf[j] === j) spf[j] = i;
      }
    }
  }
}

function primeFactorization(n) {
  const factors = [];
  while (n > 1) {
    factors.push(spf[n]);
    n = Math.floor(n / spf[n]);
  }
  return factors;
}

sieve();
const number = 999983; // example input
console.log(`Prime factors of ${number}:`, primeFactorization(number).join(' '));

package main

import "fmt"

const MAX = 1000000
var spf [MAX + 1]int

func sieve() {
    for i := 1; i <= MAX; i++ {
        spf[i] = i
    }
    spf[1] = 1
    for i := 2; i * i <= MAX; i++ {
        if spf[i] == i {
            for j := i * i; j <= MAX; j += i {
                if spf[j] == j {
                    spf[j] = i
                }
            }
        }
    }
}

func primeFactorization(n int) []int {
    factors := []int{}
    for n > 1 {
        factors = append(factors, spf[n])
        n /= spf[n]
    }
    return factors
}

func main() {
    sieve()
    number := 999983 // example input
    fmt.Printf("Prime factors of %d: ", number)
    for _, f := range primeFactorization(number) {
        fmt.Printf("%d ", f)
    }
    fmt.Println()
}

const MAX: usize = 1_000_000;

fn sieve() -> Vec<usize> {
    let mut spf = vec![0; MAX + 1];
    for i in 1..=MAX {
        spf[i] = i;
    }
    spf[1] = 1;
    let limit = (MAX as f64).sqrt() as usize;
    for i in 2..=limit {
        if spf[i] == i {
            let mut j = i * i;
            while j <= MAX {
                if spf[j] == j {
                    spf[j] = i;
                }
                j += i;
            }
        }
    }
    spf
}

fn prime_factorization(mut n: usize, spf: &Vec<usize>) -> Vec<usize> {
    let mut factors = Vec::new();
    while n > 1 {
        factors.push(spf[n]);
        n /= spf[n];
    }
    factors
}

fn main() {
    let spf = sieve();
    let number = 999_983; // example input
    let factors = prime_factorization(number, &spf);
    print!("Prime factors of {}: ", number);
    for f in factors {
        print!("{} ", f);
    }
    println!();
}

const val MAX = 1000000
val spf = IntArray(MAX + 1)

fun sieve() {
    for (i in 1..MAX) spf[i] = i
    spf[1] = 1
    var i = 2
    while (i * i <= MAX) {
        if (spf[i] == i) {
            var j = i * i
            while (j <= MAX) {
                if (spf[j] == j) spf[j] = i
                j += i
            }
        }
        i++
    }
}

fun primeFactorization(n: Int): List<Int> {
    var num = n
    val factors = mutableListOf<Int>()
    while (num > 1) {
        factors.add(spf[num])
        num /= spf[num]
    }
    return factors
}

fun main() {
    sieve()
    val number = 999_983
    print("Prime factors of $number: ")
    for (f in primeFactorization(number)) {
        print("$f ")
    }
    println()
}

let MAX = 1_000_000
var spf = [Int](repeating: 0, count: MAX + 1)

func sieve() {
    for i in 1...MAX {
        spf[i] = i
    }
    spf[1] = 1
    let limit = Int(Double(MAX).squareRoot())
    for i in 2...limit {
        if spf[i] == i {
            var j = i * i
            while j <= MAX {
                if spf[j] == j {
                    spf[j] = i
                }
                j += i
            }
        }
    }
}

func primeFactorization(_ n: Int) -> [Int] {
    var num = n
    var factors = [Int]()
    while num > 1 {
        factors.append(spf[num])
        num /= spf[num]
    }
    return factors
}

sieve()
let number = 999_983
print("Prime factors of \(number): \(primeFactorization(number).map{String($0)}.joined(separator: " "))")

const MAX = 1000000;
const spf: number[] = new Array(MAX + 1);

function sieve(): void {
  for (let i = 1; i <= MAX; i++) spf[i] = i;
  spf[1] = 1;
  for (let i = 2; i * i <= MAX; i++) {
    if (spf[i] === i) {
      for (let j = i * i; j <= MAX; j += i) {
        if (spf[j] === j) spf[j] = i;
      }
    }
  }
}

function primeFactorization(n: number): number[] {
  const factors: number[] = [];
  while (n > 1) {
    factors.push(spf[n]);
    n = Math.floor(n / spf[n]);
  }
  return factors;
}

sieve();
const number = 999983; // example input
console.log(`Prime factors of ${number}:`, primeFactorization(number).join(' '));

Time complexity

Space complexity

O(N)

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.