A Prime Number calculator using a Template Class

So we all know that a prime number has only two factors, being one and itself? A first attempt at writing a function to tell if a given number is prime might look like this:

constexpr bool isPrime(int n) {
    for (int i = 2; (i * i) < n; ++i) {
        if (!(n % i)) {
            return false;
        }
    }
    return true;
}

The structure is straightforward, we loop over the semi-open range [2,√n) and break on the first occurrence (if any) of the loop counter being a factor of n.

However this is inefficient as non-prime numbers are needlessly checked for being factors, to avoid this we would need a list of prime numbers handy, again up to √n. (We’ve also restricted ourselves to checking ints.) Of course, being C++ programmers we don’t say global state, we say data encapsulated by a class. Here is a sketch of a suitable class:

template <typename T>
class Primes<T> {
    vector<T> primes_cache{ 2, 3, 5, 7, 11 /* ... */ };
public:
    bool isPrime(T n) {
        for (const auto& p : primes_cache) {
            if (!(n % p)) {
                return false;
            }
            if ((p * p) >= n) {
                return true;
            }
        }
        throw runtime_error("Insufficient primes in cache");
    }
};

Here we loop over the primes_cache vector using a range-for loop, again checking for factors. Importantly, we use a generic class introduced with the template keyword; a correct definition of a Primes object would thus be:

Primes<unsigned> primes{};

A way to use the single member function would be:

bool twenty_five_isprime = primes.isPrime(25);

However we’re still not done, as we need a way to populate the cache as needed to avoid throwing an exception. To avoid code duplication, this would need to call isPrime() which could result in infinite recursion if we’re not careful. Here is a program which demonstrates the complete class:

#include <vector>
#include <stdexcept>
#include <iostream>

using namespace std;

template <typename T = unsigned>
class Primes {
    vector<T> primes_cache{ 2, 3 };
    typename vector<T>::size_type cache_step;
    void generate(typename vector<T>::size_type step) {
        auto new_size = primes_cache.size() + step;
        auto p = primes_cache.back();
        while (primes_cache.size() < new_size) {
            if (isPrime(++p, false)) {
                primes_cache.push_back(p);
            }
        }
    }
public:
    Primes(typename vector<T>::size_type step = 1000)
        : cache_step{ step } {
        generate((step > 2) ? step - 2 : step);
    }
    template <typename U>
    bool isPrime(const U& n, bool gen = true) {
        while (gen && ((primes_cache.back() * primes_cache.back()) <= n)) {
            generate(cache_step);
        }
        for (const auto& p : primes_cache) {
            if (!(n % p)) {
                return false;
            }
            if ((p * p) >= n) {
                return true;
            }
        }
        throw runtime_error("Insufficient primes in cache");
    }
};

int main() {
    Primes<unsigned long long> primes{};
    for (unsigned i = 2; i < 200; ++i) {
        if (primes.isPrime(i)) {
            cout << i << ' ';
        }
    }
    cout << '\n';
}

Line 10 sets the default type for the primes cache; note this can be different from the type of the number being checked which is line 28. Lines 14-22 define a new private member function called generate() which populates the primes cache, calling isPrime() as needed with the generate flag set to false. Lines 29-42 are similar to code seen before, with primes_cache.back() being the value of the largest prime in the cache.

For maximum safety (that is, minimal risk of integer overflow) no types are hardcoded into the definition of this class, in particular the local variables are declared auto and cache_step uses type vector<T>::size_type. This is good C++ practice, and something you should emulate in your own code; any incompatibilities can most likely be resolved at compile-time. Of course, we are free to use arbitrary precision number types instead of unsigned or unsigned long long, but while correct these will probably not be useful in practice with current hardware as they will be too slow.

The other consideration is multithreading: this class is not thread safe as there are no checks against writing to primes_cache. This could be solved quite easily using a mutex member variable and a lock guard for the while-loop in the generate() function, thus allowing multiple threads to call isPrime() and potentially achieving quicker performance on multi-core machines.

If you’re interested in creating a list of known primes another way, there is the Sieve of Eratosthenes which could be a use case for std::vector<bool>. Of course, it is always good practice to benchmark against an alternative method with regards to space and time.

Resources: Download or browse the source code