C++ で巨大素数を判定・生成する

(1/1)
Python を使った最も基本的なプログラムとして、画面（ターミナル）にメッセージを表示するプログラムを作る。1行メッセージを表示するものと、プログラムが得意とする繰り返し処理を使った複数行のメッセージを表示する、2つのプログラムを作っていく。
>C++で巨大素数を判定・生成する
「PHPで巨大素数の生成と判定」をC++に移植した。同じGMPライブラリを使用し、コマンドライン・プログラムなので、Windowsだけではなく、他のOSでも動作するソース・プログラムになっている。

（2024年7月7日）使用ライブラリ更新
（2024年2月17日）英語表記追加(-eオプション)，使用ライブラリ等を更新
（2023年10月8日）使用ライブラリ更新

目次

  1. サンプル・プログラム
  2. 使用ライブラリ
  3. ビルド
  4. 解説：ミラー・ラビン素数判定プログラム
  5. 解説：指定した桁数の巨大素数を求める
  6. 解説：コマンドラインオプションの定義と取得
  7. 解説：指定した文字列が整数かどうかを判定する
  8. 参考サイト

サンプル・プログラム

download ダウンロード

圧縮ファイルの内容
bigprime.exe実行プログラム本体（CUI版）
bigprime.cppソース・プログラム
makefileビルドファイル
bigprime.cpp 更新履歴
バージョン 更新日 内容
1.1.1 2024/07/07 使用ライブラリ更新
1.1.0 2024/02/17 英語表記追加(-eオプション)，使用ライブラリ等を更新
1.0.2 2023/10/08 使用ライブラリ更新
1.0.1 2023/05/28 使用ライブラリ更新
1.0.0 2023/03/12 初版

使用ライブラリ

多倍長整数演算するためにライブラリ GMP が必要になる。
コマンドライン・オプションを操作する場合などに、オープンソースのライブラリ Boost C++ライブラリが必要になる。
各々の導入方法等については、「C++ 開発環境の準備」をご覧いただきたい。

ビルド

ビルドするには 同梱の "makefile" を利用してほしい。

解説：ミラー・ラビン素数判定プログラム

/**
 * べき剰余を求める．
 * @param  mpz_class base 基数
 * @param  mpz_class exp  指数
 * @param  mpz_class mod  除数
 * @return mpz_class べき剰余
*/
mpz_class modpow(mpz_class base, mpz_class exp, mpz_class mod) {
	mpz_class res = 1;
	while (exp > 0) {
		if ((exp & 1) == 1) {
			res = (res * base) % mod;
		}
		base = (base * base) % mod;
		exp >>= 1;
	}
	return res;
}

/**
 * 指定した整数をミラー・ラビン判定法を使って素数かどうかを判定する．
 * @param	mpz_class n  判定したい整数
 * @return	bool true:素数である／false:素数でない
*/
bool millerRabinPrimalityTest(mpz_class n) {
	if (n <= 1)		return false;
	if (n == 2)		return true;
	if (n % 2 == 0)	return false;
	vector A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
	mpz_class s = 0, d = n - 1;
	while (d % 2 == 0) {
		s++;
		d >>= 1;
	}
	for (auto a : A) {
		if (a % n == 0)	return true;
		mpz_class t, x = modpow(a, d, n);
		if (x != 1) {
			for (t = 0; t < s; ++t) {
				if (x == n - 1)		break;
				x = x * x % n;
			}
			if (t == s)	return false;
		}
	}
    return true;
}
ミラー・ラビン素数判定については、「PHPとPythonで巨大素数を扱う」をご覧いただきたい。

mpz_classはGMPの多倍長整数のC++によるラッパークラスで、四則演算など、多倍長整数計算をintとほぼ同じように取り扱うことができる。

解説：指定した桁数の巨大素数を求める

/**
 * 指定した桁数の巨大素数を求める．
 * @param	mpz_class *prime 素数を格納する
 * @param	long num 桁数
 * @return	なし
*/
void getBigPrime(mpz_class *prime, unsigned long num) {
	bool ret;

	//多倍長整数構造体を初期化する．
	mpz_t a;
	mpz_init(a);
	mpz_t n;
	mpz_init(n);
	mpz_t b;
	mpz_init_set_ui(b, 10);
	mpz_pow_ui(n, b, num);

	//メルセンヌ・ツイスタ法で疑似乱数生成器のステート構造体を初期化する．
	gmp_randstate_t state;
	gmp_randinit_default(state);
	//時間をseedにする．
	time_t rtime;
	time(&rtime);
	gmp_randseed_ui(state, rtime);

	//10万回まで乱数を発生させ，素数だったら戻り値にする．
	for (unsigned i = 0; i < 100000; i++) {
		//乱数を求める
		mpz_urandomm(a, state, n);
		*prime = (mpz_class)a;
		//素数かどうか判定する
		ret = millerRabinPrimalityTest(*prime);
		if (ret)	break;
	}

	//後処理
	mpz_clear(a);
	gmp_randclear(state);
}
ユーザー関数 getBigPrime は、指定した桁数の多倍長整数の乱数を発生させ、それを前述のmillerRabinPrimalityTestに渡して素数かどうかを判定する。素数だったら、それを戻り値にする。

解説：コマンドラインオプションの定義と取得

	//コマンドライン・オプションの定義
	options_description options("コマンドライン・オプション");
	options.add_options()
		("number,n", value(), "桁数")
		("time,t",    "計算時間表\示")
		("en,e",      "英語表\示")
		("help,h",    "ヘルプ")
		("version,v", "バージョン情報")
		;
	//コマンドライン・オプションの取得
	variables_map vm;
	try {
		store(parse_command_line(argc, argv, options), vm);
	} catch(const boost::program_options::error_with_option_name& e) {
		ErrorMessage =  e.what();
		cerr << ErrorMessage << endl;
		return 1;
	}
	notify(vm);
コマンドラインオプションの定義と取得を行うのに、Boost C++ Librariesの Boost Program Options Libraryを利用した。
オプションの定義は、options_description型によって行う。
parse_command_line関数が、options_description の定義にしたがってコマンドライン引数を解析し、その結果を variables_map オブジェクトに格納するよう指示する。notify関数を実行することで、はじめて variables_mapオブジェクトに解析結果が格納される。 
	//英語表示
	if (vm.count("en")) {
		flagEnglish = true;
	}
	//ヘルプ情報を表示する．
	if (vm.count("help")) {
		dispHelp(flagEnglish);
	//バージョン情報
	} else if (vm.count("version")) {
		dispVersion(flagEnglish);
コマインドラインオプションが指定されているかどうかは、cout関数を用いて判定する。
オプションの後に指定された値は、vm["オプション"].as<データ型>() のようにして取り出すことができる。 
	//素数判定または生成
	} else {
		//計算時間表示
		if (vm.count("time")) {
			flagTime = true;
		}
		//計算開始時刻
		clock_t t0 = clock();
		//素数生成
		if (vm.count("number")) {
			unsigned long num = (unsigned long)vm["number"].as();
			if (num <= 0) {
				num = 100;
			}
			getBigPrime(&prime, num);
			cout << prime;
		//素数判定
		} else if (argc > 1) {
			bool flagJudge = false;
			for (int i = 1; i < argc; i++) {
				if (isInteger((string)argv[i])) {
					mpz_class num = (mpz_class)argv[i];
					bool ret = millerRabinPrimalityTest(num);
					if (! flagEnglish) {
						if (ret) {
							cout << "素数です";
						} else {
							cout << "素数ではありません";
						}
					} else {
						if (ret) {
							cout << "prime number";
						} else {
							cout << "not prime number";
						}
					}
					flagJudge = true;
					break;
				}
			}
			//ヘルプ情報を表示する．
			if (! flagJudge) {
				dispHelp(flagEnglish);
			}
		//ヘルプ情報を表示する．
		} else {
			dispHelp(flagEnglish);
		}
		//計算完了時刻
コマンドラインに指定した数字が素数かどうかを判定するときは、コマンドラインオプションではないため、main 関数に渡される argc, argv を舐めてみて、整数（isInteger）があれば素数判定を実行する。無ければヘルプを表示する。

解説：指定した文字列が整数かどうかを判定する

/**
 * 指定した文字列が整数かどうかを判定する．
 * @param	string str 文字列
 * @return	boot true：整数である／整数でない
*/
bool isInteger(const string str) {
	for (char const& c : str) {
		if (std::isdigit(c) == 0) {
			return false;
		}
	}
	return true;
}
C++には、文字列が整数が同化を判定する関数が用意されていないため、自作した。
1つ1つの文字が数字かどうかを判定する組み込み関数 isdigit を繰り返し実行する。

参考サイト

（この項おわり）
前へ 目次 次へ
関連ページ tweet
Valid HTML5 正当なCSSです!
2023年03月23日 作成／2024年07月14日 更新
Copyright by studio pahoo, (C)2023-2024
（※）本ページはリンクフリーですが、複製・転載時にはご一報ください。
★本ページへのご意見・ご質問・お便りは、こちらへお願いします。
header
ホーム  > Web技術  > C++でWindowsアプリ開発