logo标签列表

在C++编译过程中检查数字是否为质数

c++compilationc-preprocessorprimes
8

我有一个模板类，它以无符号整数为模板参数，但我必须确保该数字是素数。例如，我可以在构造函数中检查它，但最好在编译期间进行检查。

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

template <bool statement>
class Assert;

template <>
struct Assert<true> {};

我可以在任何将被编译的代码中简单地创建这种类型的对象，使用我的条件作为参数，如果该条件为false，则不会编译。问题是我必须检查某个数字是否为质数。假设这个数字是n。

我想到了包含一个单独的文件"PrimeTest.h"，并尝试通过从该文件内部包含相同的文件来将n除以从n-1到1的每个数字。这是我如何使用它的：

#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 指令。你有任何想法吗？
你使用的编译器是什么？你能够使用C++11的任何特性吗？ - Yakk - Adam Nevraumont
我正在使用Microsoft Visual C++，但它还不支持constexpr。 但没关系，我已经通过使用额外的模板结构来应对这个问题。 - Danylo Fitel
没错，它们大致相等。如果你只需要小质数，@CygnusX1的答案就足够了。我下面给出的constexpr答案可以适用于基于template的解决方案，如果你需要更大的数字。 - Yakk - Adam Nevraumont
5个回答
6
你不需要预处理器来在编译时计算某些内容。通常，当需要计算时，你可以使用模板元编程（或chris在他的答案中建议的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;
};

只有当数字 2、3、... D 不能整除 N 时，值 tmp<N,D>::result 才为 true。

有了上述工具，创建编译时检查器 is_prime 就相当容易了：

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

现在编译时的值is_prime<N>::result，当N是质数时为true，否则为false。这个值可以提供给其他模板使用，比如你的Assert。
我撤回了建议的 std::integral_constant，因为 (a) 它是 C++11 的特性，而上面的解决方案坚持使用旧的 C++。使用 C++11，chris 的 constexpr 更加干净。 (b) 因为如果这样做，is_prime<N>::result 就不存在了，但我在下面的段落中仍然引用它。 - CygnusX1
6

这是一个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) 次，这意味着 C++11 标准要求编译器实现的 constexpr 表达式最小递归限制为 512 不再是问题。

带有调试嵌入的在线示例。

这将在您的系统上基本上适用于 std::size_t 的限制。我已经使用 111111113 进行了测试。

这在 中非常容易，因为我们不再需要一行 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;  
}
让2、3和5起作用也很容易。这只需要做target == 2 || target%2 != 0（在括号中）。而0和1可以通过target >= 2来处理。 - chris
@chris 是的，我最初发布的代码中有一些错误。上面的“二叉树”版本应该是可以工作的，除了0和1之外...让我去修复它们。 - Yakk - Adam Nevraumont
嘿，那不会很有趣吗。我通常不做这种事情，所以有点有趣。 - chris
is_prime(361) 返回 true，但 361 = 19 x 19 不是质数。 - tnt
1
@tntxtnt 抱歉，我的分治算法出现了一处差一错误。已修复。 - Yakk - Adam Nevraumont
显示剩余2条评论
3
这是一种业余的解决方案，适用于正数并在编译时完成，但在递归限制达到之前无法进行太多计算。我认为可以添加一个手动计算的平方根参数，以允许它扩展到目前的平方数。然而，它确实利用了C++11的constexpr函数，使语法更易于使用且不需要额外的工作。无论如何，这可能是一个不错的开始，期待看到更好的解决方案。
constexpr bool IsPrime(std::size_t N, std::size_t I = 2) {
    return (N !=  2 ? N%I : true) //make 2 prime and check divisibility if not 2
        && (N >= 2) //0 and 1 are not prime
        && (I >= N-1 ? true : IsPrime(N, I+1)); //stop when I is too big
}

你甚至可以让计算平方根的工作自动完成。在这个例子中，我将把IsPrime转换成一个辅助函数，以便只能使用N来调用IsPrime：

//basically does ceil(sqrt(N))
constexpr std::size_t Sqrt(std::size_t N, std::size_t I = 2) {
    return I*I >= N ? I : Sqrt(N, I+1);
}

//our old IsPrime function with no default arguments; works with sqrt now
constexpr bool IsPrimeHelper(std::size_t N, std::size_t sqrt, std::size_t I) {
    return (N != 2 ? N%I : true) 
        && (N >= 2) 
        && (I >= sqrt ? true : IsPrimeHelper(N, sqrt, I+1));
}

//our new prime function: this is the interface for the user
constexpr bool IsPrime(std::size_t N) {
    return IsPrimeHelper(N, Sqrt(N), 2);
}

对于我来说，这个新版本可以在其他版本失败的情况下使用数字521。它甚至可以使用数字9973。新预期的高度应该是旧高度的平方。如果你想再进一步，甚至可以修改IsPrimeHelper，当I为2时递增1，当I不为2时递增2。这将导致一个大约是当前版本两倍的新高度。

我期望一个 IsPrime 函数只需要一个参数。为什么你要传入两个参数呢？不过，使用 constexpr 的想法很好。我还在思考“旧”的 C++…… - CygnusX1
1
@CygnusX1，这只是为了将所需实体数量减少到一个。您可以将其包装在仅使用一个参数并使用第二个参数2调用此函数的东西中，而不是默认值。您仍然可以像这样使用它：static_assert(IsPrime(11), "11不是质数。");。 - chris
@CygnusX1，我决定加入平方根的想法，并在此过程中制作了您的助手 :) - chris
constexpr的建议最大递归深度为512。在素数（2之后）之间采用步长为2可以使您的代码效率提高一倍，而采用步长为6（仅在前6个数字之后检查X+1和X+5）可以再提高50%的效率。 - Yakk - Adam Nevraumont
@Yakk，我在实现平方根的想法后开始建议将其放在底部 :) - chris
0
您可以使用此constexpr在编译时检查小于n < 51529的数字是否为质数：
static constexpr auto is_prime_51529(const int n) {
    // will not be repeated 7 times
    return (n > 1) & ((n < 6) * 42 + 0x208A2882) >> n % 30 && (n < 49 || n % 7 && n % 11 && n % 13 && n % 17 && n % 19 && n % 23 && n % 29 && n % 31 && n % 37 && n % 41 && n % 43 && n % 47 && (n < 2809 || 53 && n % 59 && n % 61 && n % 67 && n % 71 && n % 73 && n % 79 && n % 83 && n % 89 && n % 97 && n % 101 && n % 103 && n % 107 && n % 109 && n % 113 && n % 127 && n % 131 && n % 137 && n % 139 && n % 149 && n % 151 && n % 157 && n % 163 && n % 167 && n % 173 && n % 179 && n % 181 && n % 191 && n % 193 && n % 197 && n % 199 && n % 211 && n % 223));
}
0

对于传统的C编译器而言，需要一个可移植的东西：

// preprocessor-compatible macro telling if x is a prime at most 15-bit
#define PRIME15(x) (((x)>1)&(((x)<6)*42+545925250)>>((x)%30&31)&&((x)<49\
||(x)%7&&(x)%11&&(x)%13&&(x)%17&&(x)%19&&(x)%23&&(x)%29&&(x)%31&&(x)%37\
&&(x)%41&&(x)%43&&(x)%47&&((x)<2809||(x)%53&&(x)%59&&(x)%61&&(x)%67\
&&(x)%71&&(x)%73&&(x)%79&&(x)%83&&(x)%89&&(x)%97&&(x)%101&&(x)%103\
&&(x)%107&&(x)%109&&(x)%113&&(x)%127&&(x)%131&&(x)%137&&(x)%139&&(x)%149\
&&(x)%151&&(x)%157&&(x)%163&&(x)%167&&(x)%173&&(x)%179&&(x)<32761)))
  • (x)>1 因为所有的质数都至少是2
  • (x)<6 因为我们特殊处理了质数2、3、5
  • 42 是这些特殊质数的位图 (1<<2)+(1<<3)+(1<<5)
  • 545925250 是1、7、11、13、17、19、23、29的位图，用于快速测试2、3、5的可除性
  • >>((x)%30&31) 访问上述快速测试的位图¹
  • (x)<49 (或者 (x)<2809 和 (x)<32761) 因为我们想要告诉7=√49 (或者53=√2809和181=√32761)是质数
  • (x)%7&..&&(x)%47 和 (x)%53&&..&&(x)%179 因为我们测试可除性
  • 179 因为下一个质数的平方超过了15位。
如果宏用于生成代码，那么它非常高效。

在线试用！

¹ &31 是一种解决负数 x 警告的 hack。但是，将第一个 & 替换为 &&1& 对于某些嵌入式 CPU 的编译器来说并不可行。在最高警告级别下，该编译器会报告常量表达式中包含负移位的错误，包括短路布尔运算需要不进行求值的子表达式。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接