在C++编译期间检查数字是否为素数

Question

我有一个模板类,它将无符号整数作为模板参数,但我必须确保该数字是素数.例如,我可以在构造函数中检查它,但在编译期间最好这样做.

这是我正在使用的Assert模板:

template <bool statement>
class Assert;

template <>
struct Assert<true> {};

我可以使用我的条件作为参数在任何要编译的代码中创建这种类型的对象,如果该条件为false则不会编译.问题是我必须检查一些数字是否为素数.让它成为n.

我想出了包含一个单独的文件"PrimeTest.h"的想法,并尝试通过在该文件中包含相同的文件将n从n-1除以n.这就是我使用它的方式:

#define SUSPECT n
#include "PrimeTest.h"

这是"PrimeTest.h":

#ifdef SUSPECT

    #ifndef CURRENT
        #define CURRENT (SUSPECT-1)
    #endif // CURRENT

    #ifndef FINISHED

    #if CURRENT>100
        #define IS_PRIME
        #define FINISHED
    #else
        #if SUSPECT%CURRENT==0
            #define IS_NOT_PRIME
            #define FINISHED
        #else
            #define CURRENT (CURRENT-1)  // THAT DOES NOT WORK!!!
            #include "PrimeTest.h"
        #endif // SUSPECT % CURRENT != 0
    #endif

    #endif // FINISHED

#endif // SUSPECT

但问题出在这里:我无法以任何方式减少CURRENT,包括临时值和#pragma push_macro指令.任何想法如何做到这一点？

Answer 1

您不需要预处理器来在编译时计算某些东西.通常,在需要计算时,您可以使用模板元编程(或constexpr克里斯在他的答案中建议的功能)

通过模板元编程,您可以按如下方式解决任务:

首先定义一个模板,该模板可以在编译时检查给定值N是否为可分数D或者任何低于D大于1的值.

template <int N, int D>
struct tmp {
    static const bool result = (N%D) && tmp<N,D-1>::result;
};

template <int N>
struct tmp<N,1> {
    static const bool result = true;
};

该值tmp<N,D>::result是true只有当数字2,3,... D不分裂N.

使用上面的工具,创建is_prime编译时检查器相当简单:

template <int N>
struct is_prime {
    static const bool result = tmp<N,N-1>::result;
};

现在,编译时间值is_prime<N>::result是true时N是素数,false否则.该值可以提供给其他模板,例如Assert您的模板.

Answer 2

C++ 11 constexpr版本应该能够在任何实现建议的递归深度限制的编译器上检查大约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;  
}