Generating prime numbers at compile time
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 ;).
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