読者です 読者をやめる 読者になる 読者になる

Boost.Multiprecision ミラー・ラビン法による素数判定

C++

多倍長演算ライブラリであるBoost.Multiprecisionには、ミラー・ラビン法による素数判定のための関数、miller_rabin_test()が定義されています。これは、乱数を使用して素数かどうかを判定する関数です。

// <boost/multiprecision/miller_rabin.hpp>
namespace boost {
namespace multiprecision {

  template <class Engine>
  bool miller_rabin_test(const number-or-expression-template-type& n, unsigned trials, Engine& gen);
  bool miller_rabin_test(const number-or-expression-template-type& n, unsigned trials);

}}

以下のようにして使います:

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
#include <boost/random/mersenne_twister.hpp>

namespace mp = boost::multiprecision;

int main()
{
    boost::random::mt19937 gen;
    for (int i = 2; i < 20; ++i) {
        bool is_prime = mp::miller_rabin_test(i, 25, gen);
        std::cout << i << " is " << (is_prime ? "prime" : "not prime") << std::endl;
    }
}
2 is not prime
3 is prime
4 is not prime
5 is prime
6 is not prime
7 is prime
8 is not prime
9 is not prime
10 is not prime
11 is prime
12 is not prime
13 is prime
14 is not prime
15 is not prime
16 is not prime
17 is prime
18 is not prime
19 is prime

この関数の第1引数には、素数判定したい奇数を指定します。偶数を指定するとfalseが返ります。
第2引数は、試行回数です。大きい値を指定するほど、正しく素数判定できる確率が高くなります。
第3引数は、内部で使用する乱数生成エンジンへの参照です。第3引数を指定しない場合、boost::random::mt19937のstaticオブジェクトが作られます。