我对如何在编译时生成素数数组很感兴趣(我相信唯一的方法是使用元编程(在 C++ 中,不确定它在其他语言中是如何工作的))。
快速说明,我不想只是说 int primes[x] = {2, 3, 5, 7, 11, ...};
,因为我想在竞争性编程中使用这种方法,其中源文件不能大于10KB。所以这排除了任何超过几千个元素的预生成数组。
例如,我知道您可以在编译时生成斐波那契数列,但这相当容易,因为您只需添加最后 2 个元素。对于素数,我真的不知道如何在没有循环的情况下做到这一点(我相信这是可能的,但我不知道如何使用递归,我猜),而且我不知道如何在编译时评估循环-时间。
所以我正在寻找一个关于如何解决这个问题的想法(至少),甚至可能是一个简短的例子
最佳答案
我们可以做一个 编译时间 的预计算一些 素数并将它们放入编译时生成的数组中。然后使用简单的查找机制来获取值。这仅适用于少量素数。但它应该向您展示基 native 制。
我们将首先定义一些用于计算素数的默认方法为 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, ...>
与相应的数字,由生成器计算。我们创建了一个 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 位值的所有斐波那契数。所以,一个相当灵活的 helper 。
警告
大数组大小会导致编译器出现堆外错误。
使用 Microsoft Visual Studio Community 2019 版本 16.8.2 进行开发和测试。
另外使用 clang11.0 和 gcc10.2 编译和测试
语言:C++17
关于c++ - 在编译时生成素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/66239693/