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

Croton

Since C++14, you might use loop in constexpr function. – Araxes

Logically, if you succeed to do a function (without memory allocation until C++20), you probably can just add constexpr before. Else, provide your non-constexpr function and ask how to transform it into constexpr. – Araxes

Not quite what you seek, but for examples of how to compute the nth prime at compile time (with some conditions) have a look at #15290178 – Sizzle

I didnt mention it in the answer, but did you consider to calculate a list of prime numbers at runtime and use that (via copy paste) to declare a compile time array in the actual code? Its much less fun, but probably also much simpler – Devonna

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

Gibeon

"I do not think that there is a faster way to calculate the n'th prime number." From scratch, maybe not, but here, we might have access to previous prime numbers. – Araxes

I guess this should be for (size_t i = 2; i*i <= n; i++) in the isPrime – Nonesuch

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 ;).

Devonna

I don't want to be rude, but you are being overly wordy :P – Delia

@Delia not rude at all. Its rather verbose on purpose, not meant to be copypasted as is. OP seems to have no clue at all how to approach it, so I just wanted to feed them with something, not necessarily the actual solution – Devonna

Ahaha, sorry, I've been to cryptic. I was referring to something like int constexpr prime_numbers = do you see my user name?. I was obviously joking :P – Delia

@Delia ah ok, my research on 463035818 being the largest is almost done, next i'll focus on proving that it is the only prime number. Once thats done, I'll update the answer accordingly. – Devonna

I'm pretty sure that with "correct" ring, it is provable :-) – Araxes

@largest_prime_is_463035818 Yeah, I was relatively clueless, thank you for answer – Croton

@Croton afaik the template fibonacci example was never meant to be acutally used to get fibonacci numbers at compile-time (I'd use a simple table if I needed it), but rather to demonstrate what can be done with templates. My answer is somehow in the same spirit: It shows how it can be done, but I don't think I would actually ever use this. The other answer is more focused on getting some "real code" – Devonna

Answer 3

With "simple" constexpr, you might do:

template <std::size_t N>
constexpr void fill_next_primes(std::array<std::size_t, N>& a, std::size_t n)
{
    std::size_t i = (a[n - 1] & ~0x1) + 1;
    while (!std::all_of(a.begin(), a.begin() + n, [&i](int e){ return i % e != 0; })) {
        i += 2;
    }
    a[n] = i;
}

template <std::size_t N>
constexpr std::array<std::size_t, N> make_primes_array()
{
    // use constexpr result
    // to ensure to compute at compile time,
    // even if `make_primes_array` is not called in constexpr context
    constexpr auto res = [](){
        std::array<std::size_t, N> res{2};
        
        for (std::size_t i = 1; i != N; ++i) {
            fill_next_primes(res, i);
        }
        return res;
        }();
    return res;
}

Demo

Araxes