Generating prime numbers at compile time

Question

I am interested in how you can generate an array of prime numbers at compile time (I believe that the only way is using metaprogramming (in C++, not sure how this works in other languages)).

Quick note, I don't want to just say int primes[x] = {2, 3, 5, 7, 11, ...};, since I want to use this method in competitive programming, where source files cannot be larger than 10KB. So this rules out any pregenerated arrays of more than a few thousand elements.

I know that you can generate the fibonacci sequence at compile time for example, but that is rather easy, since you just add the 2 last elements. For prime numbers, I don't really know how to do this without loops (I believe it is possible, but I don't know how, using recursion I guess), and I don't know how loops could be evaluated at compile-time.

So I'm looking for an idea (at least) on how to approach this problem, maybe even a short example

Answer 1

We can do a compile time pre calculation of some prime numbers and put them in a compile time generated array. And then use a simple look up mechanism to get the value. This will work only to a small count of prime numbers. But it should show you the basic mechanism.

We will first define some default approach for the calculation a prime number as a constexpr function:

constexpr bool isPrime(size_t n) noexcept {
    if (n <= 1) return false;
    for (size_t i = 2; i*i < n; i++)    if (n % i == 0) return false;
    return true;
}
constexpr unsigned int primeAtIndex(size_t i) noexcept {
    size_t k{3};
    for  (size_t counter{}; counter < i; ++k)
        if (isPrime(k)) ++counter;
    return k-1;
}

With that, prime numbers can easily be calculated at compile time. Then, we fill a std::array with all prime numbers. We use also a constexpr function and make it a template with a variadic parameter pack.

We use std::index_sequence to create a prime number for indices 0,1,2,3,4,5, ....

That is straigtforward and not complicated:

// Some helper to create a constexpr std::array initilized by a generator function
template <typename Generator, size_t ... Indices>
constexpr auto generateArrayHelper(Generator generator, std::index_sequence<Indices...>) {
    return std::array<decltype(std::declval<Generator>()(size_t{})), sizeof...(Indices) > { generator(Indices)... };
}

This function will be fed with an index sequence 0,1,2,3,4,... and a generator function and return a std::array<return type of generator function, ...> with the corresponding numbers, calculated by the generator.

We make a next function, that will call the above with the index sequence 1,2,3,4,...Max, like so:

template <size_t Size, typename Generator>
constexpr auto generateArray(Generator generator) {
    return  generateArrayHelper(generator, std::make_index_sequence<Size>());
}

And now, finally,

constexpr auto Primes = generateArray<100>(primeAtIndex);

will give us a compile-time std::array<unsigned int, 100> with the name Primes containing all 100 prime numbers. And if we need the i'th prime number, then we can simply write Primes [i]. There will be no calculation at runtime.

I do not think that there is a faster way to calculate the n'th prime number.

Please see the complete program below:

#include <iostream>
#include <utility>
#include <array>

// All done during compile time -------------------------------------------------------------------
constexpr bool isPrime(size_t n) noexcept {
    if (n <= 1) return false;
    for (size_t i = 2; i*i < n; i++)    if (n % i == 0) return false;
    return true;
}
constexpr unsigned int primeAtIndex(size_t i) noexcept {
    size_t k{3};
    for  (size_t counter{}; counter < i; ++k)
        if (isPrime(k)) ++counter;
    return k-1;
}
// Some helper to create a constexpr std::array initilized by a generator function
template <typename Generator, size_t ... Indices>
constexpr auto generateArrayHelper(Generator generator, std::index_sequence<Indices...>) {
    return std::array<decltype(std::declval<Generator>()(size_t{})), sizeof...(Indices) > { generator(Indices)... };
}
template <size_t Size, typename Generator>
constexpr auto generateArray(Generator generator) {
    return  generateArrayHelper(generator, std::make_index_sequence<Size>());
}

// This is the definition of a std::array<unsigned int, 100> with prime numbers in it
constexpr auto Primes = generateArray<100>(primeAtIndex);
// End of: All done during compile time -----------------------------------------------------------


// Some debug test driver code
int main() {
    for (const auto p : Primes) std::cout << p << ' '; std::cout << '\n';
    return 0;
}

---

By the way. The generateArray fucntionality will of course also work with other generator functions.

If you need for example triangle numbers, then you could use:

constexpr size_t getTriangleNumber(size_t row) noexcept {
    size_t sum{};
    for (size_t i{ 1u }; i <= row; i++) sum += i;
    return sum;
}

and

constexpr auto TriangleNumber = generateArray<100>(getTriangleNumber);

would give you a compile time calculated constexpr std::array<size_t, 100> with triangle numbers.

For fibonacci numbers your could use

constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    unsigned long long f1{ 0ull }, f2{ 1ull }, f3{};
    while (index--) { f3 = f2 + f1; f1 = f2; f2 = f3; }
    return f2;
}

and

constexpr auto FibonacciNumber = generateArray<93>(getFibonacciNumber);

to get ALL Fibonacci numbers that fit in a 64 bit value.

So, a rather flexible helper.

---

Caveat

Big array sizes will create a compiler out of heap error.

---

Developed and tested with Microsoft Visual Studio Community 2019, Version 16.8.2.

Additionally compiled and tested with clang11.0 and gcc10.2

Language: C++17

Answer 2

The following is just to give you something to start with. It heavily relies on recursively instantiating types, which isn't quite efficient and I would not want to see in the next iteration of the implementation.

div is a divisor of x iff x%div == false:

template <int div,int x>
struct is_divisor_of : std::conditional< x%div, std::false_type, std::true_type>::type {};

A number x is not prime, if there is a p < x that is a divisor of x:

template <int x,int p=x-2>
struct has_divisor : std::conditional< is_divisor_of<p,x>::value, std::true_type, has_divisor<x,p-1>>::type {};

If no 1 < p < x divides x then x has no divisor (and thus is prime):

template <int x>
struct has_divisor<x,1> : std::false_type {};

A main to test it:

int main()
{
    std::cout << is_divisor_of<3,12>::value;
    std::cout << is_divisor_of<5,12>::value;
    std::cout << has_divisor<12>::value;
    std::cout << has_divisor<13>::value;
}

Output:

1010

Live Demo.

PS: You probably better take the constexpr function route, as suggested in a comment. The above is just as useful as recursive templates to calculate the fibonacci numbers (ie not really useful other than for demonstration ;).