Получить таблицу простых чисел во время компиляции

#cpp #шаблоны_с++ #простые_числа

Говорят, что шаблонное программирование началось с вычисления простых чисел. Так
что компилятор их точно может вычислить во время компиляции.
И даже я худо-бедно могу написать или переписать такой шаблон:

template
struct DoIsPrime {
    static constexpr bool value = (p%d != 0) && DoIsPrime::value;
    };

template
struct DoIsPrime {
    static constexpr bool value = (p % 2 != 0);
    };

template
struct IsPrime {
    static constexpr bool value = DoIsPrime < p, p / 2 >::value;
    };

template<>
struct IsPrime<0> {
    static constexpr bool value = false;
    };
template<>
struct IsPrime<1> {
    static constexpr bool value = false;
    };
template<>
struct IsPrime<2> {
    static constexpr bool value = true;
    };
template<>
struct IsPrime<3> {
    static constexpr bool value = true;
    };

template
bool isPrime = IsPrime
::value;


А как бы их еще и сохранить? как теперь записать таблицу простых чисел во время компиляции?
Скажем, получить

unsigned int p[] = { }


где p[i] - просто простые числа до какой-то границы? p[0]=2, p[1]=3 и так далее?
    

Ответы

Ответ 1

Воспользуюсь вашими наработками в своем ответе:

//Ваш код проверки на простоту выше
template
constexpr bool isPrime = IsPrime
::value;  //Этот тоже ваш, просто добавил constexpr  

template
struct PrimeAray;

template
struct PrimeAray : PrimeAray, numbers..., number>{

};

template
struct PrimeAray : PrimeAray, numbers...>{

};

template
struct PrimeAray<0, number, true, numbers...>{
    static const int arr[];
};

template
const int PrimeAray<0, number, true, numbers...>::arr[] = {numbers...};

int main(){
    for(int i : PrimeAray<10>::arr){
        std::cout << i << std::endl;
    }
}


На экране будет 10 простых чисел. 

Теперь что же здесь творится. Рекурсивно инстанцируем и наследуем шаблон PrimeAray.
На каждом шаге увеличиваем проверяемое число на 1. Если число простое, добавляем его
в список и уменьшаем заданное количество на 1. Когда количество станет равно 0, значит
все необходимые простые числа найдены и можно положить результат в массив и прерывать
рекурсию. 

Полный пример


Ответ 2

Вариант 1

Получаем массив простых чисел, встретившихся до заданного целого числа.

online compiler :

#include 
#include 
#include 

// Перебираем числа вплоть до заданного, складывая простые в массив.
template<::std::uint32_t value_upper_bound> constexpr auto
Collect_Primes_Impl(void)
{
    static_assert(0 < value_upper_bound);
    ::std::array<::std::uint32_t, value_upper_bound> primes{};
    primes[0] = 1;
    ::std::uint32_t primes_count{1};
    ::std::uint32_t value{1};
    while(value_upper_bound != value)
    {
        ++value;
        bool is_prime{true};
        ::std::uint32_t prime_index{1};
        while(primes_count != prime_index)
        {
            if(0 == (value % primes[prime_index]))
            {
                is_prime = false;
                break;
            }
            ++prime_index;
        }
        if(is_prime)
        {
            primes[primes_count] = value;
            ++primes_count;
        }
    }
    return ::std::make_pair(primes_count, primes);
}

// Компонуем массив простых чисел, подгоняя под надлежащий размер.
// По идее, требуемый размер можно посчитать заранее, но тогда
// придется их вычислять по два раза.
template<::std::uint32_t value_upper_bound> constexpr auto
Collect_Primes(void)
{
    static_assert(0 < value_upper_bound);
    constexpr const auto collected{Collect_Primes_Impl()};
    ::std::array<::std::uint32_t, collected.first> primes{};
    ::std::uint32_t prime_index{0};
    while(collected.first != prime_index)
    {
        primes[prime_index] = collected.second[prime_index];
        ++prime_index;
    }
    return primes;
}

constexpr const auto pr20{Collect_Primes<20>()};

static_assert(::std::size_t{9} == pr20.size());

static_assert(::std::uint32_t{ 1} == pr20[0]);
static_assert(::std::uint32_t{ 2} == pr20[1]);
static_assert(::std::uint32_t{ 3} == pr20[2]);
static_assert(::std::uint32_t{ 5} == pr20[3]);
static_assert(::std::uint32_t{ 7} == pr20[4]);
static_assert(::std::uint32_t{11} == pr20[5]);
static_assert(::std::uint32_t{13} == pr20[6]);
static_assert(::std::uint32_t{17} == pr20[7]);
static_assert(::std::uint32_t{19} == pr20[8]);


Вариант 2

Получаем массив простых чисел заданной длины.

online compiler

template<::std::size_t primes_count, typename TInt = ::std::uint64_t> constexpr auto
Collect_Primes(void)
{
    static_assert(0 < primes_count);
    ::std::array primes{};
    primes[0] = 1;
    ::std::size_t collected_primes_count{1};
    TInt value{1};
    constexpr const TInt max_value{::std::numeric_limits::max()};
    while(max_value != value)
    {
        ++value;
        bool is_prime{true};
        ::std::size_t prime_index{1};
        while(collected_primes_count != prime_index)
        {
            if(0 == (value % primes[prime_index]))
            {
                is_prime = false;
                break;
            }
            ++prime_index;
        }
        if(is_prime)
        {
            primes[collected_primes_count] = value;
            ++collected_primes_count;
            if(primes_count == collected_primes_count)
            {
                break;
            }
        }
    }
    return primes;
}