A very common problem in programming is to calculate prime numbers fast.

There are a lot of interesting ways to solve this problem. I want to show you some solutions without the need for a complex algorithm. This type of solutions can also be applied to a lot of problems that may occur during your daily work.

Let’s start with the most easiest and basic solution to print out some prime numbers:

#include <iostream>

using namespace std;

bool isPrime(int nr) {
    for (int d = 2; (d * d) <= (nr + 1); ++d)
        if (!(nr % d))
            return false;
    
    return true;
}

int main (int argc, char * const argv[]) {
    for (int i = 0; i < 50; ++i)
        if (isPrime(i))
            cout << i << endl;
}

Easy. Simple. And slow. Everything is calculated during run time.

Calculate during compile time

Another approach is to use C++ templates to calculate the whole thing during compile time. At first we need a template to check if a given number is a prime:

template<int N, int D = N - 1> struct isPrime {
    enum {
        result = (N % D) && isPrime<N, D-1>::result
    };
};
    
template<int N>
struct isPrime<N, 1> {
    enum { 
        result = true 
    };
};

The first template will check recursively if the number is a prime. The second is a specialization for the case the divisor reached or is 1.

Now you can find out, if a given number is a prime:

if (isPrime<3>::result)
    cout << "Guess what: 3 is a prime!";

The next step is to print primes in a given range. We create a print-out template, that will print out a number if a second parameter is true:

template<int N, bool ISPRIME> 
struct printIfPrime {
    static inline void print() {}
};
    
template <int N> 
struct printIfPrime<N, true> {
    static inline void print() { 
        std::cout << N << endl;
    }
};

As you see, our default print-out template does nothing, but if the second parameter is true, it will print out the number.

Next we need to recursively print out all prime numbers in the given range:

template<int N, int MAX> 
struct printPrimes {
    static inline void print()
    {
        printIfPrime<N, isPrime<N>::result>::print();
        printPrimes<N + 1, MAX>::print();
    }
};

Don’t compile this! It won’t work. The build time would be infinite, because printPrimes calls itself and recursion will never stop.

To avoid this issue, we can add the following specialisation:

template<int N> 
struct printPrimes<N, N> {
    static inline void print() {
        printIfPrime<N, isPrime<N>::result>::print();
    }
};

The template will be used when N becomes MAX and will terminate the recursion.

Finally, here is the code to print out some primes:

int main (int argc, char * const argv[]) {
    printPrimes<2, 40>::print();
    return 0;
}

The advantage of this solution is that you move execution time into compile time. Especially for games, execution time is usually more critical than compile time. The disadvantage is the increased compile time and that all input parameters must be known at compile time.

Use a lookup-table

Another very easy, but fast solution is to save a lookup-table on disk.

At first, we need to calculate everything and save it into a file:

#include <iostream>
#include <fstream>

using namespace std;

#define MAX_PRIME 200

bool isPrime(int nr) {
    for (int d = 2; (d * d) <= (nr + 1); ++d)
        if (!(nr % d))
            return false;
    
    return true;
}

struct primeLookUp {
    int nr;
    bool isPrime;
};

int main (int argc, char * const argv[]) {
    ofstream myfile;
    myfile.open("primeLookUp.dat");
    struct primeLookUp p;
    for (int i = 0; i < MAX_PRIME; ++i) {
        p.nr = i;
        p.isPrime = isPrime(i);
        myfile.write(reinterpret_cast<char*>(&p), sizeof(p));
    }
    myfile.close();
}

We saved all numbers, even the non-primes in the file, so we are able to seek through the file fast. Now we are able to look up the primes and print them out:

ifstream infile;
infile.open("primeLookUp.dat");
    
// [ ... ]

struct primeLookUp p;

for (int i = 50; i < 150; ++i) {
    infile.seekg(i * sizeof(primeLookUp));
    infile.read(reinterpret_cast<char*>(&p), sizeof(p));
    if (p.isPrime) {
        cout << p.nr << endl;
    }
}

// [ ... ]

infile.close();

If we need to check for primes very often, we can also load the file into memory:

ifstream infile;
infile.open("primeLookUp.dat");

struct primeLookUp tbl[MAX_PRIME];

for (int i = 0; i < MAX_PRIME; ++i) {
    infile.read(reinterpret_cast<char*>(&tbl[i]), sizeof(tbl[i]));
}

infile.close();

// [ ... ]
    
for (int i = 22; i < 88; ++i) {
    if (tbl[i].isPrime) {
        cout << i << endl;
    }
}
  1. Thomas (2011-02-19 02:26)

    There are far better ways. A http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes comes immediately to mind. Also, if you don’t mind skipping a few (which in most applications is probably okay — unless this is just an exercise in a class ;-) ss to skip in your loop farther by realizing the interval between primes (http://www.jstor.org/pss/2004355) — it saves time even on the sieve method because you can skip large chunks of potential numbers very quickly for large numbers instead of holding onto the sieve for the entire series.

  2. joe (2011-02-19 04:06)

    Yes, you’re right. There are much faster and better ways to calculate primes during run time.But the template-version has the advantage that it’s the most basic yet the fastest possible way because the generated code just contains constants (if you don’t care about compile time of course).

  3. Cthulhu and other crazies ยป Blog Archive » Checking for primes? Dumber algorithm is faster algorithm (2011-03-21 17:05)

    [...] Fast prime numbers (intermediaware.com) [...]

Add your comment now