Gaps Between the Primes

How this program works, piece by piece. All you need to know going in is what a prime number is.

1. The question

A prime is a whole number bigger than 1 that only divides evenly by 1 and itself: 2, 3, 5, 7, 11, 13, and so on. The gap between two primes in a row is just how far apart they are:

2 ─1─ 3 ─2─ 5 ─2─ 7 ─4─ 11 ─2─ 13 ─4─ 17 ─2─ 19 ─4─ 23 ─6─ 29

This program counts upward forever and keeps asking two questions: what's the biggest gap we've seen so far, and what's the smallest? I got the idea from Terry Tao's lecture on prime gaps (linked in the README above). The big gaps keep growing, because primes get rarer as numbers get bigger. The small gaps are a famous unsolved problem.

2. The plan

Before writing any code, here's the idea in plain English:

Start at 2 and count up by 1, forever.
For each number, check whether it's prime.
If it is, subtract the previous prime to get the gap.
If that gap is a new record (biggest or smallest), remember it.
Every so often, print what we've found.

3. The code

The whole program is one file, primegaps.cpp, about 40 lines. Here it is in pieces.

Keeping track. Five variables hold everything the program knows:

int current = 2, lastp = 2, currentp = 2, lgap = 0, sgap = 1000;

Variable	What it holds
`current`	The number we're checking right now
`lastp`	The previous prime we found
`currentp`	The newest prime we found
`lgap`	Largest gap so far. Starts at 0 so the first real gap beats it.
`sgap`	Smallest gap so far. Starts at 1000, a "big enough" number so a real gap will be smaller.

Counting forever. while (true) is a loop with no exit, so the program runs until you stop it. Each time around, current++ moves to the next number:

while (true) {
    current++;
    if (isPrime(current)) {
        // found a prime: measure the gap (next piece)
    }
}

Measuring the gap. When current is prime, the gap is the new prime minus the last one. Then we compare it to our records:

currentp = current;
int gap = currentp - lastp;
if (gap > lgap) {
    lgap = gap;          // new biggest gap
} else if (gap < sgap) {
    sgap = gap;          // new smallest gap
}
lastp = currentp;        // this prime is the "last" one next time

Printing now and then. Printing every number would flood the screen, so it only prints when current is a multiple of 12,345. The % operator gives the remainder of a division, and a remainder of 0 means "divides evenly". 12,345 isn't special; it's just a number that prints often enough to watch.

if (current % 12345 == 0) {
    cout << "--Prime Gaps--" << endl;
    cout << "current prime: " << currentp << endl;
    cout << "Lgap: " << lgap << endl;
    cout << "Sgap: " << sgap << endl;
}

Checking for primes. isPrime uses trial division: try dividing by every number from 2 up to num - 1. If any of them divides evenly, num isn't prime.

bool isPrime(int num) {
    bool flag = true;
    for (int i = 2; i < num; i++) {
        if ((num % i) == 0) {
            flag = false;
        }
    }
    return flag;
}

4. Try it in your browser

This runs the same idea in JavaScript, right on this page, with a faster prime check. Pick a limit to see how many primes are below it and every time the record gap grew.

README

Walkthrough

1. The question

2. The plan

3. The code

4. Try it in your browser