8

テンプレート パラメーターとして符号なし整数を受け取るテンプレート クラスがありますが、その数値が素数であることを確認する必要があります。たとえば、コンストラクターで確認できますが、コンパイル時に行う方がよいでしょう。

私が使用している Assert テンプレートは次のとおりです。

template <bool statement>
class Assert;

template <>
struct Assert<true> {};

条件をパラメーターとして使用して、コンパイルされるコードの一部でこのタイプのオブジェクトを作成するだけで、その条件が false の場合はコンパイルされません。問題は、いくつかの数が素数であるかどうかを確認する必要があることです。nとする。

別のファイル「PrimeTest.h」を含め、そのファイル内から同じファイルを含めることにより、n-1 から 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

しかし、ここに問題があります。一時的な値や #pragma push_macro ディレクティブを含め、考えられる方法で CURRENT をデクリメントすることはできません。それを行う方法はありますか？

4

4 に答える 4

6

constexpr提案された再帰の深さ制限を実装する任意のコンパイラで、およそ 1500 までの数値をチェックできるC++11バージョン:

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。

これは非常に簡単です。1 行の 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;  
}
于 2013-05-26T17:09:22.263 に答える