主页 / 问题 / 774045
Accepted
Mikhailo
Asked:2020-01-22 19:39:55 +0000 UTC2020-01-22 19:39:55 +0000 UTC

在编译时获取素数表

  • 772

据说模板编程是从计算素数开始的。所以编译器肯定可以在编译时计算出来。甚至我也能以某种方式编写或重写这样的模板：

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等等？

c++

2 个回答

  1. 选项1

    我们得到一个在给定整数之前遇到的素数数组。

    在线编译器：

    #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

    我们得到一个给定长度的素数数组。

    在线编译器

    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;
}
    • 3
  2. Best Answer

    我将在我的回答中使用您的工作：

    //Ваш код проверки на простоту выше
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 时，则已找到所有必要的素数，并且您可以将结果放入数组并中断递归。

    完整示例

    • 2

相关问题