Algorithms

You don't need a faster computer — you need a better algorithm.

A few years ago I put a tiny experiment on GitHub: larsommen/primes — five different programs that all answer the same dull question, how many prime numbers are there below 100,000? (The answer is 9,592.)

The interesting part isn't the answer. It's how long each program takes to get there — and what actually moves the needle. Spoiler: it isn't threads, and it isn't a faster CPU.

Press the button. Every version below runs right here in your browser, on your machine, timed live.

Count primes below 10,000 30,000 100,000 1,000,000 ▶ Run all five

JavaScript runs on one thread, so V4 (threaded) runs the same code as V3 here — which is exactly the lesson: threading parallelises a slow algorithm, it doesn't fix it. The benchmark runs in a Web Worker, so the page never freezes; any version still grinding after 10 seconds is stopped and marked "gave up" — at 1,000,000 the brute-force versions don't finish, and that's the whole point.

What each version does

The first four are variations on the same idea — take a number, try to divide it — each a little less wasteful than the last:

V1 — brute forceV2 — break earlyV3 — odds + √nV4 — threaded V3V5 — the Sieve

Check every divisor from 2 up to the number itself, and don't even stop when you've already found one. The simplest thing that works, and by far the slowest.

for (int devider = 2; devider < number; devider++)
    if (number % devider == 0) isPrime = false;   // keeps going anyway

The same loop, but break the moment a divisor is found. One word of code; roughly half the work.

if (number % devider == 0) { isPrime = false; break; }

Two real insights: even numbers above 2 are never prime (skip them), and a factor never exceeds √n (stop there). Now the work per number is tiny.

for (int devider = 3; devider <= Math.sqrt(number); devider += 2)
    if (number % devider == 0) { isPrime = false; break; }

V3, split across threads. It throws more of the machine at the problem — but the algorithm is unchanged, so the win is marginal. More hardware, same idea.

A different idea entirely. Don't test numbers at all. Assume everything is prime, then walk the primes and cross out their multiples. What survives is the set of primes. This is the leap.

for (int number = 2; number < limit; number++)
    if (!composite[number]) {
        totalPrimes++;
        for (int multiple = number * 2; multiple < limit; multiple += number)
            composite[multiple] = true;          // cross it out
    }

The point

V1 → V4 is a story of optimisation: shave a loop, add a break, add threads. Each helps a bit. V5 is a story of a better algorithm — and it leaves all the tuning in the dust on the very same computer.

That's the whole lesson, and it generalises far beyond counting primes:

You don't need a faster computer — you need a better algorithm.

Code: github.com/larsommen/primes.