在编译时生成质数

Question

我对如何在编译时生成质数数组很感兴趣（我相信唯一的方法是使用元编程（在 C++ 中，不确定这在其他语言中如何工作））。

快速说明，我不想只说 int primes[x] = {2, 3, 5, 7, 11, ...};，因为我想在竞争性编程中使用这种方法，其中源文件不能大于 10KB。所以这排除了任何超过几千个元素的预生成数组。

例如，我知道您可以在编译时生成斐波那契数列，但这相当简单，因为您只需添加最后两个元素。对于质数，我真的不知道如何在没有循环的情况下做到这一点（我相信这是可能的，但我不知道如何，我猜是使用递归），而且我不知道如何在编译时评估循环-时间。

所以我正在（至少）寻找一个关于如何解决这个问题的想法，甚至可能是一个简短的例子

Answer 1

以下只是给你一些开始。它严重依赖递归实例化类型，效率不高，我不想在下一次迭代实现中看到它。

div 是 x 的除数当且仅当 x%div == false:

template <int div,int x>
struct is_divisor_of : std::conditional< x%div, std::false_type, std::true_type>::type {};

一个数 x 不是素数，如果有一个 p < x 是 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 {};

如果没有 1 < p < x 整除 x 那么 x 没有约数（因此是素数）：

template <int x>
struct has_divisor<x,1> : std::false_type {};

一个main来测试一下：

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;
}

输出：

Live Demo.

PS：您最好按照评论中的建议采用 constexpr 函数路线。上面的内容与计算斐波那契数的递归模板一样有用（即除了演示之外没有其他用处；）。

Answer 2

我们可以对一些素数进行编译时预计算，并将它们放入编译时生成的数组中。然后使用简单的查找机制来获取值。这仅适用于少量素数。但它应该向您展示基本机制。

我们将首先定义一些计算质数的默认方法作为 constexpr 函数：

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;
}

有了它，素数就可以很容易地在编译时计算出来了。然后，我们用所有质数填充 std::array。我们还使用了一个 constexpr 函数，并使它成为一个带有可变参数包的模板。

我们使用 std::index_sequence 为索引 0,1,2,3,4,5, ....

创建素数

简单明了并不复杂:

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

此函数将输入索引序列 0,1,2,3,4,... 和一个生成函数以及 return 一个 std::array<return type of generator function, ...> 和相应的数字，通过以下方式计算发电机。

我们创建一个 next 函数，它将使用索引序列 1,2,3,4,...Max 调用上面的函数，如下所示：

template <size_t Size, typename Generator>
constexpr auto generateArray(Generator generator) {
    return  generateArrayHelper(generator, std::make_index_sequence<Size>());
}

现在，终于，

constexpr auto Primes = generateArray<100>(primeAtIndex);

将为我们提供一个编译时 std::array<unsigned int, 100>，其名称 Primes 包含所有 100 个素数。如果我们需要第 i 个质数，那么我们可以简单地写 Primes [i]。运行时不会有计算。

我认为没有更快的方法来计算第 n 个素数。

请看下面的完整程序：

#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;
}

顺便说一句。 generateArray 功能当然也可以与其他生成器功能一起使用。

如果你需要三角数，那么你可以使用：

constexpr size_t getTriangleNumber(size_t row) noexcept {
    size_t sum{};
    for (size_t i{ 1u }; i <= row; i++) sum += i;
    return sum;
}

和

constexpr auto TriangleNumber = generateArray<100>(getTriangleNumber);

会给你一个编译时间 constexpr std::array<size_t, 100> 用三角数计算。

您可以使用斐波那契数列

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;
}

和

constexpr auto FibonacciNumber = generateArray<93>(getFibonacciNumber);

获取适合 64 位值的所有斐波那契数。

所以，一个相当灵活的帮手。

警告

大数组大小将导致编译器出现堆溢出错误。

使用 Microsoft Visual Studio Community 2019 版本 16.8.2 开发和测试。

另外用clang11.0和gcc10.2编译测试

语言：C++17

Answer 3

使用“简单”constexpr，您可以：

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

在编译时生成质数

Generating prime numbers at compile time

c++

primes

metaprogramming

compile-time