Optimized Prime Miner

Mines prime numbers for as long as you let it run, and a study in making a simple program genuinely fast.

The base is the Square Root Theorem for primality testing: to check if a number is prime, you only need to test divisibility by primes up to its square root. Everything else here is about doing that with as little wasted work as possible.

The optimizations

Skip the evens. No prime above 2 is even, so stepping by 2 instead of 1 immediately halves the work.

Skip the multiples of three too (the 6k ± 1 wheel). Every prime above 3 sits right next to a multiple of six. So instead of always adding 2, the step alternates between +2 and +4: 7, 11, 13, 17, 19, 23.... That skips every multiple of 2 and 3 for free and cuts the candidates to about a third of the range.

number += gap
gap = 6 - gap    # 4, 2, 4, 2, ... forever

Memoize the primes. Every prime found is kept in a list and reused to test the next number, so nothing is ever recomputed. Numbers are tiny in memory, so hundreds of thousands of them sit in RAM comfortably (tracked live with psutil).

Skip anything ending in 0 or 5. Cheap divisibility check, kills a fifth of what's left.

Never take a square root. Instead of asking "is this prime bigger than √n?", ask "is this prime squared bigger than n?". Same question, but it's pure integer multiplication with no float precision loss and no math.sqrt call in the hottest loop of the program.

if prime * prime > n:   # instead of prime > math.sqrt(n)
    break

A data-structure note

The primes live in a plain Python list. I tested numpy arrays and dictionaries and both were slower here — numpy is built for vectorised math over big datasets, not for appending and iterating one item at a time, which is all this needs.

Run it

pip install psutil
python prime_miner.py

It prints the highest prime found, how many it has checked, RAM usage, elapsed time and primes per second, refreshing every 100,000 candidates.

Run it from a real terminal, not the PyCharm or IDLE console — the screen-clearing misbehaves there.

Write-up

Full story, including the Sieve of Eratosthenes comparison and why the GIL makes multithreading the wrong tool here: Optimized prime miner