L4. Print all Prime Factors of a Number | Maths Playlist

This chapter explores how to efficiently find and print all prime factors of a given integer $n$, transitioning from naive trial division to optimized square-root bounds and advanced factor-stripping techniques.

1. Problem Statement: What is a Prime Factor?

When given an integer $n$, the goal is to output all unique prime numbers that divide $n$ evenly without leaving a remainder.

Real-Life Analogy

Mental Hook: Think of an industrial sorting facility receiving a massive batch item (like $60$ packages). The facility breaks the batch down using foundational component sizes ($2, 3, 5$). These components cannot be broken down any further (prime numbers) and fit evenly into the total inventory.

• Example 1 ($n = 60$):

  • All divisors: $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$
  • Prime divisors (Prime Factors): $2, 3, 5$

• Example 2 ($n = 35$): Prime factors are $5, 7$

• Example 3 ($n = 780$): Standard school factorization method:

  CODE

  Copy

  780 / 2 = 390
  390 / 2 = 195
  195 / 3 = 65
  65  / 5 = 13
  13  / 13 = 1
  

  Prime factors: $2, 3, 5, 13$

2. Approach 1: The Extreme Naive Approach

The most intuitive approach is to iterate through every number from $2$ to $n$, check if it divides $n$, and then verify whether that divisor is a prime number.

Pseudo-Code / Algorithm

vector<int> primeFactors;
for (int i = 2; i <= n; i++) {
    if (n % i == 0) {
        if (isPrime(i)) {
            primeFactors.push_back(i);
        }
    }
}

Complexity Analysis

• Time Complexity: $O(n \times \sqrt{n})$ because the outer loop runs $n$ times, and the inner isPrime() check takes $O(\sqrt{n})$ time.
• Space Complexity: $O(k)$ where $k$ is the variable number of prime factors stored in the list.

3. Approach 2: Optimizing with Square Root Divisor Pairs

Building upon the divisor property from previous lectures, divisors always exist in pairs. If $i$ divides $n$, then $n / i$ is also a divisor. Thus, we only need to loop up to $\sqrt{n}$.

Core Optimization Logic

Instead of checking all the way up to $n$, we check up to $\sqrt{n}$ and test both $i$ and $n / i$.

vector<int> primeFactors;
for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        if (isPrime(i)) primeFactors.push_back(i);
        if (i != n / i && isPrime(n / i)) primeFactors.push_back(n / i);
    }
}

Complexity Analysis

• Time Complexity: Approximate $O(\sqrt{n} \times \text{primeCheck})$, but non-deterministic because isPrime() only triggers on actual factors.
• Space Complexity: Variable space for storing the answer list.

4. Approach 3: School Method with Iterative Division (Stripping Factors)

We can completely eliminate the expensive isPrime() function by using a smart school-book approach: iteratively dividing out factors as we encounter them.

Step-by-Step Flow

Pseudo-Code

vector<int> primeFactors;
for (int i = 2; i <= n; i++) {
    if (n % i == 0) {
        primeFactors.push_back(i);
        while (n % i == 0) {
            n = n / i;
        }
    }
}

Limitations of Approach 3

• If given a large prime number like $n = 37$, the loop runs all the way from $2$ to $37$.
• Worst-Case Time Complexity: $O(n)$ when the number is a large prime.

5. Approach 4: The Highly Optimized Square-Root + Factor Stripping Algorithm

To fix the large prime bottleneck while keeping the speed of factor-stripping, we combine the $\sqrt{n}$ loop limit with while-loop division and a final cleanup check.

Complete Optimized Algorithm

vector<int> primeFactors;
for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        primeFactors.push_back(i);
        while (n % i == 0) {
            n = n / i;
        }
    }
}
if (n != 1) {
    primeFactors.push_back(n);
}

Dry Run Walkthrough ($n = 780$)

1. $i = 2$: $780 \pmod 2 == 0$. Add 2. Reduce $n$ via while until $n = 195$.
2. $i = 3$: $195 \pmod 3 == 0$. Add 3. Reduce $n$ via while until $n = 65$.
3. $i = 4$: $65 \pmod 4 \neq 0$. Skip.
4. $i = 5$: $65 \pmod 5 == 0$. Add 5. Reduce $n$ via while until $n = 13$.
5. Loop Termination: Next, $i = 6$. $6 \times 6 = 36$, which exceeds the remaining $n = 13$. The loop terminates.
6. Final Check: Since remaining $n = 13 \neq 1$, add 13 to primeFactors.
7. Final Result: [2, 3, 5, 13] (Loop executed only up to $i = 6$ instead of $780$).

6. Comparison of All Approaches

Summary and Key Takeaways

• Prime Factor Definition: Prime factors are divisors of a number that are themselves prime numbers (e.g., prime factors of $60$ are $2, 3, 5$).
• Avoid Redundant Prime Checks: Using an expensive isPrime() function inside divisor loops degrades performance unnecessarily.
• Factor Stripping Technique: Dividing $n$ repeatedly inside a while (n % i == 0) loop ensures that composite multiples (like $4, 6, 8$) are automatically filtered out without extra checks.
• Square Root Bound (i * i <= n): Factors always exist in pairs around $\sqrt{n}$, limiting the search space drastically.
• The Leftover Prime Check: When looping only up to $\sqrt{n}$, a large prime factor may remain uncaptured unless a final if (n != 1) catch is executed.
• Optimal Time Complexity: The best-case and average-case time complexity drops down to $O(\sqrt{n})$, making it extremely efficient even for large inputs.