C++11constexpr版本应该能够在任何实现建议的递归深度限制的编译器上检查大约 1500 的数字：
constexpr bool is_prime_helper( std::size_t target, std::size_t check ) {
return (check*check > target) ||
(
(target%(check+1) != 0)
&& (target%(check+5) != 0)
&& is_prime_helper( target, check+6 )
);
}
constexpr bool is_prime( std::size_t target ) {
return (target != 0) && (target !=1) &&
( ( target == 2 || target == 3 || target == 5 )
|| ((target%2 != 0) && (target%3 != 0) && (target%5)!=0 &&
is_prime_helper( target, 6 )));
}
为了改善这一点，我们用二叉搜索树做一些有趣的事情：
#include <cstddef>
constexpr bool any_factors( std::size_t target, std::size_t start, std::size_t step) {
return
!(start*start*36 > target)
&&
(
( (step==1)
&& (
(target%(start*6+1) == 0)
|| (target%(start*6+5) == 0)
)
)
||
( (step > 1)
&&
(
any_factors( target, start, step/2 )
|| any_factors( target, start+step/2, step-step/2 )
)
)
);
}
然后我们像这样使用它：
constexpr bool is_prime( std::size_t target ) {
// handle 2, 3 and 5 explicitly:
return
(target == 2 || target == 3 || target == 5)
||
(
target != 0
&& target != 1
&& target%2 != 0
&& target%3 != 0
&& target%5 != 0
&& !any_factors( target, 1, target/6 + 1 ) // can make that upper bound a bit tighter, but I don't care
);
}
#include <iostream>
int main() {
std::cout << "97:" << is_prime(97) << "\n";
std::cout << "91:" << is_prime(91) << "\n";
}
这将递归〜log_2(target/6)次，这意味着constexprC ++ 11标准要求编译器至少实现的512表达式的递归限制不再是问题。
实时示例，嵌入调试。
这将基本上达到std::size_t您系统的限制。我已经用111111113.
这在c++14中非常容易，因为我们不再需要单行 constexpr 函数，而是需要理智的结构。 见这里。
constexpr bool any_factors( std::size_t target, std::size_t start, std::size_t step ) {
if (start*start*36 > target)
{
return false;
}
if (step==1)
{
bool one_mod_6 = target%(start*6+1) == 0;
bool five_mod_6 = target%(start*6+5) == 0;
return one_mod_6 || five_mod_6;
}
bool first_half = any_factors(target, start, step/2);
bool second_half = any_factors(target, start+ step/2, (step+1)/2);
return first_half || second_half;
}