Smallest Prime Factor (SPF) & Query-Based Prime Factorization

1. Problem Statement & The Query-Based Challenge

In many algorithmic applications, we are not just asked to find the prime factors of a single number, but rather to process multiple queries where each query asks for the prime factorization (with multiplicity) of a given number $N$.

Standard Prime Factorization (Single Number)

Recall how we find prime factors for a single integer $N$ (e.g., $N = 60$):

• We start testing divisors from $2$ up to $\sqrt{N}$.
• If a number divides $N$, we divide $N$ repeatedly by that divisor, recording it until it no longer divides.
• If any remainder greater than $1$ remains at the end, it is prime itself.

The Naive Approach for Multiple Queries

Suppose we are given $Q$ queries, where each query provides a number up to $10^5$.

• Naive Algorithm: For each query $i$ from $1$ to $Q$, we run our standard factorization algorithm which takes time proportional to $\mathcal{O}(\sqrt{N})$.
• Total Time Complexity: If there are $Q$ queries, the worst-case time complexity becomes $\mathcal{O}(Q \times \sqrt{N})$.
• Why this fails: If $Q$ is large (e.g., $10^5$) and $N$ is up to $10^5$, $\mathcal{O}(Q \sqrt{N})$ will result in a Time Limit Exceeded (TLE) in competitive programming and production systems.

2. Core Mental Model: Why We Need Smallest Prime Factor (SPF)

Real-Life Analogy: The Postal Sorting Facility

Real-Life Analogy: Imagine you run a massive shipping warehouse where customers constantly bring packages labeled with tracking numbers (queries). Each package needs to be broken down into its fundamental component parts.

• The Naive Way: Every time a package arrives, you pull out a magnifying glass and test every single prime number from $2$ up to the square root of the weight to see what divides it. This is extremely slow.
• The SPF Way: Before opening the warehouse, you hire an expert logistics clerk who creates a permanent directory book listing the Smallest Prime Factor (SPF) for every possible weight up to $10^5$. When a package arrives, you look up its weight in the directory in $\mathcal{O}(1)$ time, instantly know what prime number divides it, divide the package, and repeat until fully factorized.

By pre-computing the Smallest Prime Factor (SPF) for all numbers up to the maximum possible value using a variation of the Sieve of Eratosthenes, we reduce query time from $\mathcal{O}(\sqrt{N})$ down to $\mathcal{O}(\log N)$ per query.

3. Naive vs. Optimized Prime Factorization Code

To understand the transition, let us look at how standard prime factorization is structured and how we adapt it for prime factorization with duplicacy.

Naive Prime Factorization Function

public List<Integer> getPrimeFactors(int n) {
    List<Integer> factors = new ArrayList<>();
    // Start from the smallest prime, 2
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.add(i); // Add the prime factor with multiplicity
            n /= i;
        }
    }
    // If n is still greater than 1, the remaining part is prime
    if (n > 1) {
        factors.add(n);
    }
    return factors;
}

The Bottleneck

When $N$ is a prime number (e.g., $17$), the loop runs all the way up to $\sqrt{17}$, performing unnecessary divisions and checks. Across $Q$ queries, this becomes computationally expensive.

4. Step-by-Step Evolution: Building the SPF Array

To eliminate the $\mathcal{O}(\sqrt{N})$ loop during queries, we construct an array SPF of size $N_{\max} + 1$.

Step 1: Initialization

We create an array SPF where every index initially stores itself. For example, if our maximum number is $30$:

Index:  0  1  2  3  4  5  6  7  8  9 ... 30
SPF:    0  1  2  3  4  5  6  7  8  9 ... 30

(Note: Indices $0$ and $1$ are ignored or handled separately as they have no prime factors).

Step 2: Sieve-Based SPF Marking

We adapt the Sieve of Eratosthenes algorithm:

1. We start from $i = 2$.
2. If SPF[i] == i, it means $i$ is a prime number.
3. Instead of marking multiples as crossed out (true/false), we update their SPF value to $i$, only if SPF[j] has not already been marked with a smaller prime factor.
4. To optimize, we start marking multiples from $i \times i$, because smaller multiples of $i$ (like $2 \times i$, $3 \times i$) would have already been marked by smaller prime numbers.

5. Complete Flow Walkthrough: Sieve Construction up to $N = 30$

Let's trace how the SPF array is populated for numbers up to $30$:

Initial State (Indices hold their own values):
SPF[2..30] = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ..., 30]

1. Processing i = 2:
   - 2 is prime (SPF[2] == 2).
   - Mark multiples starting from 2*2 = 4 up to 30 with SPF = 2:
     SPF[4]=2, SPF[6]=2, SPF[8]=2, SPF[10]=2, SPF[12]=2, ..., SPF[30]=2.

2. Processing i = 3:
   - 3 is prime (SPF[3] == 3).
   - Mark multiples starting from 3*3 = 9 up to 30 with SPF = 3 (if not already marked):
     SPF[9]=3, SPF[15]=3, SPF[21]=3, SPF[27]=3.
     (Note: 12 is already marked with 2, which is smaller than 3, so we do not overwrite it!)

3. Processing i = 4:
   - 4 is not prime (SPF[4] != 4, it is 2). Skip.

4. Processing i = 5:
   - 5 is prime (SPF[5] == 5).
   - Mark multiples starting from 5*5 = 25 up to 30 with SPF = 5:
     SPF[25]=5.

6. Query Execution Walkthrough Using SPF

Once the SPF array is pre-computed, answering a query for any number $N$ becomes extremely fast. Let's trace how we factorize $N = 30$ and $N = 16$ using SPF:

Example A: Factorizing $N = 30$

1. Initial state: n = 30
2. Look up SPF[30]: We get 2.
   • Output/store 2.
   • Update n = 30 / 2 = 15.
3. Look up SPF[15]: We get 3.
   • Output/store 3.
   • Update n = 15 / 3 = 5.
4. Look up SPF[5]: We get 5.
   • Output/store 5.
   • Update n = 5 / 5 = 1.
5. n becomes 1. Stop.
   • Resulting Factorization: [2, 3, 5]

Example B: Factorizing $N = 16$ (Worst-Case for SPF)

1. Initial state: n = 16
2. Look up SPF[16]: 2 $\rightarrow$ n = 8
3. Look up SPF[8]: 2 $\rightarrow$ n = 4
4. Look up SPF[4]: 2 $\rightarrow$ n = 2
5. Look up SPF[2]: 2 $\rightarrow$ n = 1
   • Resulting Factorization: [2, 2, 2, 2]
   • Note: Even in the worst-case scenario (powers of 2), the number of steps is bounded by $\log_2(N)$.

7. Complete Implementation Code (Pseudo-code / Java-style)

Here is the complete implementation incorporating the pre-computation sieve and query handler:

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

public class PrimeFactorizationSPF {

    // Pre-compute SPF up to maximum constraint (e.g., 10^5)
    static final int MAX = 100000;
    static int[] spf = new int[MAX + 1];

    // Step 1: Pre-computation using Sieve of Eratosthenes
    public static void computeSPF() {
        // Initialize SPF array with its own index
        for (int i = 1; i <= MAX; i++) {
            spf[i] = i;
        }

        // Sieve logic starting from 2
        for (int i = 2; i * i <= MAX; i++) {
            // Check if i is prime
            if (spf[i] == i) {
                // Mark multiples of i starting from i * i
                for (int j = i * i; j <= MAX; j += i) {
                    // Only update if it hasn't been marked by a smaller prime
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
    }

    // Step 2: Query function to get prime factorization in O(log N)
    public static List<Integer> getPrimeFactorization(int n) {
        List<Integer> factorization = new ArrayList<>();
        
        while (n > 1) {
            int smallestPrime = spf[n];
            factorization.add(smallestPrime);
            n /= smallestPrime;
        }
        
        return factorization;
    }

    public static void main(String[] args) {
        // Initialize pre-computations once
        computeSPF();

        // Sample Queries
        int[] queries = {12, 16, 60, 17, 25};
        
        for (int q : queries) {
            List<Integer> factors = getPrimeFactorization(q);
            System.out.println("Factorization of " + q + ": " + factors);
        }
    }
}

8. Complexity Analysis

9. Summary and Key Takeaways

• Limitation of Naive Approach: Standard trial division up to $\sqrt{N}$ per query results in an inefficient $\mathcal{O}(Q \times \sqrt{N})$ time complexity, which times out for large query volumes ($Q$).
• The SPF Concept: Smallest Prime Factor (SPF) stores the smallest prime divisor for every number up to a predefined maximum limit.
• Sieve Integration: We build the SPF array efficiently in $\mathcal{O}(N \log(\log N))$ time using an optimized variation of the Sieve of Eratosthenes.
• Optimization of Inner Loops: When marking multiples during sieve construction, we start at $i \times i$ and only update entries where spf[j] == j to preserve the smallest prime factor.
• Logarithmic Query Time: Once SPF is pre-computed, answering each factorization query takes $\mathcal{O}(\log N)$ time by repeatedly dividing $n$ by spf[n] until $n = 1$.
• Space-Time Tradeoff: We trade $\mathcal{O}(N)$ extra space for the SPF array to achieve lightning-fast query performance in production and competitive programming environments.