目次
サンプル・プログラム
| bigprime.exe | 実行プログラム本体（CUI版） |
| bigprime.cpp | ソース・プログラム |
| makefile | ビルドファイル |
| バージョン | 更新日 | 内容 |
|---|---|---|
| 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 | 初版 |
使用ライブラリ
コマンドライン・オプションを操作する場合などに、オープンソースのライブラリ Boost C++ライブラリが必要になる。
各々の導入方法等については、「C++ 開発環境の準備」をご覧いただきたい。
ビルド
解説：ミラー・ラビン素数判定プログラム
159: /**
160: * べき剰余を求める．
161: * @param mpz_class base 基数
162: * @param mpz_class exp 指数
163: * @param mpz_class mod 除数
164: * @return mpz_class べき剰余
165: */
166: mpz_class modpow(mpz_class base, mpz_class exp, mpz_class mod) {
167: mpz_class res = 1;
168: while (exp > 0) {
169: if ((exp & 1) == 1) {
170: res = (res * base) % mod;
171: }
172: base = (base * base) % mod;
173: exp >>= 1;
174: }
175: return res;
176: }
178: /**
179: * 指定した整数をミラー・ラビン判定法を使って素数かどうかを判定する．
180: * @param mpz_class n 判定したい整数
181: * @return bool true:素数である／false:素数でない
182: */
183: bool millerRabinPrimalityTest(mpz_class n) {
184: if (n <= 1) return false;
185: if (n == 2) return true;
186: if (n % 2 == 0) return false;
187: vector<mpz_class> A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
188: mpz_class s = 0, d = n - 1;
189: while (d % 2 == 0) {
190: s++;
191: d >>= 1;
192: }
193: for (auto a : A) {
194: if (a % n == 0) return true;
195: mpz_class t, x = modpow(a, d, n);
196: if (x != 1) {
197: for (t = 0; t < s; ++t) {
198: if (x == n - 1) break;
199: x = x * x % n;
200: }
201: if (t == s) return false;
202: }
203: }
204: return true;
205: }
mpz_classはGMPの多倍長整数のC++によるラッパークラスで、四則演算など、多倍長整数計算をintとほぼ同じように取り扱うことができる。
解説：指定した桁数の巨大素数を求める
207: /**
208: * 指定した桁数の巨大素数を求める．
209: * @param mpz_class *prime 素数を格納する
210: * @param long num 桁数
211: * @return なし
212: */
213: void getBigPrime(mpz_class *prime, unsigned long num) {
214: bool ret;
215:
216: //多倍長整数構造体を初期化する．
217: mpz_t a;
218: mpz_init(a);
219: mpz_t n;
220: mpz_init(n);
221: mpz_t b;
222: mpz_init_set_ui(b, 10);
223: mpz_pow_ui(n, b, num);
224:
225: //メルセンヌ・ツイスタ法で疑似乱数生成器のステート構造体を初期化する．
226: gmp_randstate_t state;
227: gmp_randinit_default(state);
228: //時間をseedにする．
229: time_t rtime;
230: time(&rtime);
231: gmp_randseed_ui(state, rtime);
232:
233: //10万回まで乱数を発生させ，素数だったら戻り値にする．
234: for (unsigned i = 0; i < 100000; i++) {
235: //乱数を求める
236: mpz_urandomm(a, state, n);
237: *prime = (mpz_class)a;
238: //素数かどうか判定する
239: ret = millerRabinPrimalityTest(*prime);
240: if (ret) break;
241: }
242:
243: //後処理
244: mpz_clear(a);
245: gmp_randclear(state);
246: }
解説：コマンドラインオプションの定義と取得
254: //コマンドライン・オプションの定義
255: options_description options("コマンドライン・オプション");
256: options.add_options()
257: ("number,n", value<unsigned long>(), "桁数")
258: ("time,t", "計算時間表\示")
259: ("en,e", "英語表\示")
260: ("help,h", "ヘルプ")
261: ("version,v", "バージョン情報")
262: ;
263: //コマンドライン・オプションの取得
264: variables_map vm;
265: try {
266: store(parse_command_line(argc, argv, options), vm);
267: } catch(const boost::program_options::error_with_option_name& e) {
268: ErrorMessage = e.what();
269: cerr << ErrorMessage << endl;
270: return 1;
271: }
272: notify(vm);
オプションの定義は、options_description型によって行う。
parse_command_line関数が、options_description の定義にしたがってコマンドライン引数を解析し、その結果を variables_map オブジェクトに格納するよう指示する。notify関数を実行することで、はじめて variables_mapオブジェクトに解析結果が格納される。
274: //英語表示
275: if (vm.count("en")) {
276: flagEnglish = true;
277: }
278: //ヘルプ情報を表示する．
279: if (vm.count("help")) {
280: dispHelp(flagEnglish);
281: //バージョン情報
282: } else if (vm.count("version")) {
283: dispVersion(flagEnglish);
オプションの後に指定された値は、vm["オプション"].as<データ型>() のようにして取り出すことができる。
284: //素数判定または生成
285: } else {
286: //計算時間表示
287: if (vm.count("time")) {
288: flagTime = true;
289: }
290: //計算開始時刻
291: clock_t t0 = clock();
292: //素数生成
293: if (vm.count("number")) {
294: unsigned long num = (unsigned long)vm["number"].as<unsigned long>();
295: if (num <= 0) {
296: num = 100;
297: }
298: getBigPrime(&prime, num);
299: cout << prime;
300: //素数判定
301: } else if (argc > 1) {
302: bool flagJudge = false;
303: for (int i = 1; i < argc; i++) {
304: if (isInteger((string)argv[i])) {
305: mpz_class num = (mpz_class)argv[i];
306: bool ret = millerRabinPrimalityTest(num);
307: if (! flagEnglish) {
308: if (ret) {
309: cout << "素数です";
310: } else {
311: cout << "素数ではありません";
312: }
313: } else {
314: if (ret) {
315: cout << "prime number";
316: } else {
317: cout << "not prime number";
318: }
319: }
320: flagJudge = true;
321: break;
322: }
323: }
324: //ヘルプ情報を表示する．
325: if (! flagJudge) {
326: dispHelp(flagEnglish);
327: }
328: //ヘルプ情報を表示する．
329: } else {
330: dispHelp(flagEnglish);
331: }
332: //計算完了時刻
解説：指定した文字列が整数かどうかを判定する
145: /**
146: * 指定した文字列が整数かどうかを判定する．
147: * @param string str 文字列
148: * @return boot true：整数である／整数でない
149: */
150: bool isInteger(const string str) {
151: for (char const& c : str) {
152: if (std::isdigit(c) == 0) {
153: return false;
154: }
155: }
156: return true;
157: }
1つ1つの文字が数字かどうかを判定する組み込み関数 isdigit を繰り返し実行する。
参考サイト
- PHPで巨大素数の生成と判定：ぱふぅ家のホームページ
- PHPとPythonで巨大素数を扱う：ぱふぅ家のホームページ
- C++ 開発環境の準備：ぱふぅ家のホームページ
（2024年2月17日）英語表記追加(-eオプション)，使用ライブラリ等を更新
（2023年10月8日）使用ライブラリをバージョンアップ
（2023年5月28日）使用ライブラリをバージョンアップ