多倍長演算ライブラリである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オブジェクトが作られます。
