c++ 在编译时生成素数

mwkjh3gx  于 2023-05-02  发布在  其他
关注(0)|答案(3)|浏览(130)

我对如何在编译时生成素数数组很感兴趣(我相信唯一的方法是使用元编程(在C++中,不确定这在其他语言中是如何工作的)。
快速注意,我不想只说int primes[x] = {2, 3, 5, 7, 11, ...};,因为我想在竞争性编程中使用这种方法,其中源文件不能大于10KB。所以这就排除了任何超过几千个元素的预生成数组。
例如,我知道你可以在编译时生成斐波那契序列,但这相当容易,因为你只需要添加最后两个元素。对于素数,我真的不知道如何在没有循环的情况下做到这一点(我相信这是可能的,但我不知道如何使用递归,我猜),我不知道如何在编译时计算循环。
所以我在寻找一个想法(至少)如何处理这个问题,甚至可能是一个简短的例子

erhoui1w

erhoui1w1#

我们可以在编译时对一些素数进行预计算,并将它们放入编译时生成的数组中。然后使用一个简单的查找机制来获取值。这将只对一小部分素数起作用。但它应该向你展示了基本的机制。
我们将首先定义一些默认的方法来计算一个素数作为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,...和生成器函数,并返回由生成器计算的具有相应数字的std::array<return type of generator function, ...>
我们创建下一个函数,它将调用上面的索引序列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>的编译时间。
对于Fibonacci数

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

9fkzdhlc

9fkzdhlc2#

以下只是给予你一些开始。它严重依赖于递归地示例化类型,这不是很有效,我不想在实现的下一次迭代中看到。
divx的除数当且仅当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 < xx的除数:

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

输出:

1010

Live Demo
PS:你可能最好走constexpr函数路线,就像评论中建议的那样。上述是一样有用的递归模板计算斐波纳契数(即没有真正有用的其他比示范;).

z2acfund

z2acfund3#

使用“simple”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

相关问题