🚀 From Hours to Milliseconds: A Journey Through Code Optimization

Every developer writes a brute-force solution at some point — often just to get things working.
But what if that quick-and-dirty function was silently tanking your performance?

In this post, we’ll explore how to go from slow and clunky to blazing fast, using one deceptively simple problem: checking if a number is prime.

---

🧩 The Problem: is_prime(n)

We want a function that checks if a number is prime. Easy to describe. Easy to get wrong.

Let’s start with a naive solution and work our way up.

---

🐌 Step 1: Naive Brute Force (Please Don’t)

def is_prime(n: int):
    factors_count = 0
    for i in range(1, n + 1):
        if n % i == 0:
            factors_count += 1
    return factors_count == 2

🔻 What’s wrong here? It checks every number from 1 to n. Try this with 10,000 numbers? Pack a lunch.

⸻

⚙️ Step 3: Basic Divisibility

def is_prime(n: int):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

✅ Exits early on the first divisor — a decent start, but still O(n).

⸻

⚡ Step 4: Skip Even Numbers

def is_prime(n: int):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, n, 2):
        if n % i == 0:
            return False
    return True

🧠 Insight: Half the numbers are even. Skip them.

Result: ~2× faster in practice.

⸻

🧮 Step 5: Square Root Optimization

import math

def is_prime(n: int):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

🏃‍♂️ Loop now runs √n times, not n. That’s a massive upgrade.

⸻

🧠 Step 6: The 6k ± 1 Trick

def is_prime(n: int):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

💡 Why this works: All primes > 3 are of the form 6k ± 1. Fewer checks = faster results.

⸻

🧪 Benchmark Results

We ran each function on 10,000 numbers (from 100,000 to 110,000):

Version Relative Time (best = 1.0) Step 3: Basic Loop ~2.24× slower Step 4: Skip Even ~1.00× Step 5: √n Optimization ~0.01× (fastest) Step 6: 6k ± 1 Rule ~0.01× (fastest)

⚠️ Step 1 took too long to even finish.

⸻

🧠 Optimization Takeaways

This wasn’t just about prime numbers. It’s a mini-lesson in performance thinking: • ✅ Exit early when possible • 🧹 Cut unnecessary work (e.g., skip evens, stop at √n) • 🧠 Use mathematical structure where it exists • ⏱️ Always measure — not guess

⸻

🧵 Final Thoughts

You don’t need to over-optimize everything.

But knowing how and when to optimize makes you a better developer — and a faster one, too.

The humble is_prime() function is a beautiful example: • Start naive • Refine the logic • Eliminate waste • Apply theory

⸻

🔎 Try This Next

Apply the same optimization mindset to: • Sorting algorithms • String search • Matrix multiplications • I/O-heavy tasks

Thanks for reading — and happy optimizing! 🚀