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

209
24 января 2018, 15:47

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

template<unsigned p, unsigned d>
struct DoIsPrime {
    static constexpr bool value = (p%d != 0) && DoIsPrime<p,d-1>::value;
    };
template<unsigned p>
struct DoIsPrime<p, 2> {
    static constexpr bool value = (p % 2 != 0);
    };
template<unsigned p>
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<unsigned p>
bool isPrime = IsPrime<p>::value;

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

unsigned int p[] = { }

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

Answer 1

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

//Ваш код проверки на простоту выше
template<unsigned p>
constexpr bool isPrime = IsPrime<p>::value;  //Этот тоже ваш, просто добавил constexpr  
template<int size, int number = 2, bool prime = true, int... numbers>
struct PrimeAray;
template<int size, int number, int... numbers>
struct PrimeAray<size, number, true, numbers...> : PrimeAray<size - 1, number + 1, isPrime<number + 1>, numbers..., number>{
};
template<int size, int number, int... numbers>
struct PrimeAray<size, number, false, numbers...> : PrimeAray<size, number + 1, isPrime<number + 1>, numbers...>{
};
template<int number, int... numbers>
struct PrimeAray<0, number, true, numbers...>{
    static const int arr[];
};
template<int number, int... numbers>
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, значит все необходимые простые числа найдены и можно положить результат в массив и прерывать рекурсию.

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

Answer 2

Вариант 1

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

online compiler :

#include <array>
#include <cstdint>
#include <cstddef>
// Перебираем числа вплоть до заданного, складывая простые в массив.
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<value_upper_bound>()};
    ::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<TInt, primes_count> primes{};
    primes[0] = 1;
    ::std::size_t collected_primes_count{1};
    TInt value{1};
    constexpr const TInt max_value{::std::numeric_limits<TInt>::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;
}
READ ALSO
Запуск файла из ресурсов

Запуск файла из ресурсов

Подскажите можно ли бинарный файл (exe ) запухнуть в ресурсы?

220
Внедрение из 32-битной программы 64-битной dll в 64-битный процесс, возможно ли?

Внедрение из 32-битной программы 64-битной dll в 64-битный процесс, возможно ли?

Добрый вечерДля внедрение dll в сторонний процесс использую метод из книги Рихтера

176
Почему Qt Qreator не видит им же созданные файлы?

Почему Qt Qreator не видит им же созданные файлы?

В панели файлов я не вижу файлов и первоначальный стандартный проект не компилируетсяИду просто по начальным видео урокам, но не вижу файлов

259
TextToSpeech stop() не работает

TextToSpeech stop() не работает

Я пытаюсь остановить TextToSpeech по нажатию на кнопку назадНо речь не прерывается, даже если я закрою приложение (только когда очищу кэш — Синтезатор...

202