🚀 The Power of Optimization: Finding Factors Efficiently

Today I decided to talk about time complexity and have chosen a very small, easy, direct problem - probably something you might have encountered in school. It’s a perfect example to demonstrate how a simple mathematical insight can dramatically improve performance, turning what would be years of computation into mere seconds.

📝 Problem Statement

Finding all factors of a number is a common computational task. For a number N, we need to find all integers that divide N without a remainder.

For example:

• Factors of 12: 1, 2, 3, 4, 6, 12 (total: 6 factors)
• Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24 (total: 8 factors)

💡 Our Initial Thought Process

When first approaching this problem, the brute force solution seems obvious:

1. Iterate through all numbers from 1 to N
2. Check if each number divides N without a remainder
3. Count the total number of factors

This approach works, but what happens when N becomes extremely large?

fun countFactorsBruteForce(n: Int): Int {
    var count = 0
    for (i in 1..n) {
        if (n % i == 0) {
            count++
        }
    }
    return count
}

For a number like 10^18, this would take approximately 10^10 seconds, which is over 316 years! Clearly, we need a better approach.

🤯 Our Intuition & “Aha!” Moment

We initially thought we could optimize by only checking up to N/2, but through a dry run, we realized this wasn’t correct.

Let’s see why with an example using N = 12:

With the N/2 approach, we would only check numbers 1 through 6 and count each factor once. This gives us 4 factors (1, 2, 3, 6), missing 4 and 12.

With the √N approach, we only check numbers 1 through 3 (since √12 ≈ 3.46), but for each factor i, we also count N/i as a factor. This correctly gives us all 6 factors (1, 2, 3, 4, 6, 12).

Then came the mathematical insight: If i is a factor of N, then N/i is also a factor of N.

This means:

• For every factor i < √N, there’s a corresponding factor N/i > √N
• We only need to check numbers up to √N!

For example, with N = 12:

• 1 × 12 = 12
• 2 × 6 = 12
• 3 × 4 = 12

By checking only up to √12 ≈ 3.46, we can find all factors!

🏆 Our Optimized Approach

🔹 Steps to Solve Efficiently

1. Iterate from 1 to √N
2. For each number i that divides N, count both i and N/i as factors
3. Handle the special case where i = √N (we should only count it once)

💻 Code Implementation (Kotlin)

📊 Measuring Execution Time

Let’s measure the execution time for each approach individually to see the difference in performance.

🔸 Brute Force Approach

First, let’s measure the execution time of the brute force approach:

As we can see, even for a relatively small number like 1,000,000, the brute force approach takes a noticeable amount of time. For truly large numbers, it becomes impractical.

🔸 Optimized Approach

Now, let’s measure the execution time of our optimized approach:

The optimized approach is significantly faster, allowing us to handle much larger numbers efficiently.

🔸 Side-by-Side Comparison

Let’s compare both approaches directly:

As you can see from the results, the brute force approach quickly becomes impractical as the number grows, while the optimized approach remains efficient even for very large numbers.

⏳ Time Complexity Analysis

• Brute Force Approach: O(N)
• Optimized Approach: O(√N)

For N = 10^15:

• Brute Force: ~100 years (theoretical calculation)
• Optimized: Actual measurement shown in the code above

For N = 10^18:

• Brute Force: ~316 years (theoretical calculation)
• Optimized: ~10 seconds (estimated based on O(√N) complexity)

As you can see from our actual measurements, the optimized approach makes calculations practical that would otherwise take years with the brute force approach. That’s the power of optimization! 🚀

🔥 What We Learned from This Optimization

• ✅ Mathematical insights can dramatically reduce computational complexity
• ✅ Always question your initial assumptions and verify with dry runs
• ✅ Small optimizations can make the difference between impossible and practical solutions
• ✅ Understanding the problem deeply often reveals elegant solutions

This optimization technique isn’t just theoretical—it’s the difference between a solution that would take centuries and one that completes in seconds.

Let’s continue exploring the fascinating world of algorithm optimization together!