在编译时生成素数
我对如何在编译时生成素数数组很感兴趣（我相信唯一的方法是使用元编程（在 C++ 中，不确定它在其他语言中是如何工作的））。
快速说明，我不想只说int primes[x] = {2, 3, 5, 7, 11, ...};，因为我想在竞争性编程中使用这种方法，其中源文件不能大于10KB。所以这排除了任何超过几千个元素的预生成数组。
例如，我知道您可以在编译时生成斐波那契数列，但这相当容易，因为您只需添加最后 2 个元素。对于素数，我真的不知道如何在没有循环的情况下做到这一点（我相信这是可能的，但我不知道如何，我猜是使用递归），而且我不知道如何在编译时评估循环-时间。
所以我正在寻找一个关于如何解决这个问题的想法（至少），甚至可能是一个简短的例子
回答
以下只是给你一些开始。它严重依赖递归实例化类型，这不是很有效，我不想在实现的下一次迭代中看到。
div是xiff的除数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 {};
Amain来测试一下：
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
现场演示。
PS：您可能最好按照constexpr评论中的建议采用功能路线。上面的内容与计算斐波那契数的递归模板一样有用（即，除了用于演示之外，并没有真正有用；）。
- Ahaha, sorry, I've been to cryptic. I was referring to something like `int constexpr prime_numbers = do you see my user name?`. I was obviously joking 😛
- @Enlico ah ok, my research on 463035818 being the largest is almost done, next i'll focus on proving that it is the only prime number. Once thats done, I'll update the answer accordingly.
- I'm pretty sure that with "correct" [ring](https://en.wikipedia.org/wiki/Algebra_over_a_field#Algebras_and_rings), it is provable 🙂
回答
我们可以对一些素数进行编译时预计算，并将它们放入编译时生成的数组中。然后使用简单的查找机制来获取值。这仅适用于少量素数。但它应该向您展示基本机制。
我们将首先定义一些用于计算素数作为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用所有素数填充 a 。我们还使用了一个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, ...>由生成器计算出的带有相应数字的a 。
我们创建了一个 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;
}
顺便一提。该generateArrayfucntionality当然会还与其他发电机职能的工作。
如果您需要例如三角形数字，那么您可以使用：
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