我对如何在编译时生成素数数组很感兴趣(我相信唯一的方法是使用元编程(在C++中,不确定这在其他语言中是如何工作的)。
快速注意,我不想只说int primes[x] = {2, 3, 5, 7, 11, ...};
,因为我想在竞争性编程中使用这种方法,其中源文件不能大于10KB。所以这就排除了任何超过几千个元素的预生成数组。
例如,我知道你可以在编译时生成斐波那契序列,但这相当容易,因为你只需要添加最后两个元素。对于素数,我真的不知道如何在没有循环的情况下做到这一点(我相信这是可能的,但我不知道如何使用递归,我猜),我不知道如何在编译时计算循环。
所以我在寻找一个想法(至少)如何处理这个问题,甚至可能是一个简短的例子
3条答案
按热度按时间erhoui1w1#
我们可以在编译时对一些素数进行预计算,并将它们放入编译时生成的数组中。然后使用一个简单的查找机制来获取值。这将只对一小部分素数起作用。但它应该向你展示了基本的机制。
我们将首先定义一些默认的方法来计算一个素数作为
constexpr
函数:有了它,素数可以在编译时轻松计算。然后,我们用所有素数填充
std::array
。我们还使用了一个constexpr
函数,并使其成为一个带有可变参数包的模板。我们使用
std::index_sequence
为索引0,1,2,3,4,5,....这很简单,也不复杂:
该函数将被馈送索引序列0,1,2,3,4,...和生成器函数,并返回由生成器计算的具有相应数字的
std::array<return type of generator function, ...>
。我们创建下一个函数,它将调用上面的索引序列1,2,3,4...Max,像这样:
现在终于
将给予我们一个编译时
std::array<unsigned int, 100>
,其名称为Primes,包含所有100个素数。如果我们需要第i个素数,那么我们可以简单地写Primes [i]
。在运行时不会有计算。我不认为有更快的方法来计算第n个素数。
请参阅下面的完整程序:
顺便说一下,
generateArray
函数当然也可以与其他生成器函数一起工作。如果你需要例如三角形数,那么你可以用途:
和
会给予你一个用三角形数计算的
constexpr std::array<size_t, 100>
的编译时间。对于Fibonacci数
和
得到所有符合64位值的斐波那契数。
一个相当灵活的助手。
注意事项
大的数组大小会产生编译器堆外错误。
使用Microsoft Visual Studio Community 2019版本16开发和测试。8.2.
使用clang11编译和测试。0和gcc10。2
语言:C++17
9fkzdhlc2#
以下只是给予你一些开始。它严重依赖于递归地示例化类型,这不是很有效,我不想在实现的下一次迭代中看到。
div
是x
的除数当且仅当x%div == false
:一个数
x
不是素数,如果有一个p < x
是x
的除数:如果没有
1 < p < x
整除x
,则x
没有除数(因此是素数):一个
main
来测试它:输出:
Live Demo。
PS:你可能最好走
constexpr
函数路线,就像评论中建议的那样。上述是一样有用的递归模板计算斐波纳契数(即没有真正有用的其他比示范;).z2acfund3#
使用“simple”
constexpr
,您可以执行以下操作:Demo