目次
サンプル・プログラム
| perfectNumber.exe | 実行プログラム本体（CUI版） |
| perfectNumber.cpp | ソース・プログラム |
| makefile | ビルドファイル |
| バージョン | 更新日 | 内容 |
|---|---|---|
| 1.0.1 | 2025/02/22 | 使用ライブラリ更新 |
| 1.0.0 | 2024/11/02 | 初版 |
使用ライブラリ
コマンドライン・オプションを操作する場合などに、オープンソースのライブラリ Boost C++ライブラリが必要になる。
各々の導入方法等については、「C++ 開発環境の準備」をご覧いただきたい。
ビルド
解説：総当たりで完全数を求める
perfectNumber.cpp
190: /**
191: * 完全数を出力する（総当たり計算）
192: * @param unsigned long num 探索範囲の最大桁数
193: * @param unsigned method 0:通常判定, 1:高速判定
194: * @return なし
195: */
196: void putPerfectNumberForce(unsigned long num, unsigned method) {
197: unsigned long maxInteger = pow(10, num);
198:
199: unsigned int index = 1;
200: for (unsigned long i = 2; i <= maxInteger; i++) {
201: bool res;
202: if (method == 0) {
203: res = isPerfectNumber(i);
204: } else {
205: res = isPerfectNumberRapid(i);
206: }
207: if (res) {
208: std::cout << index << ": " << i << endl;
209: index++;
210: }
211: }
212: }
perfectNumber.cpp
142: /**
143: * 完全数かどうかを判定する（通常版）
144: * @param unsigned long n 判定する値
145: * @return bool TRUE:完全数である / FALSE:完全数ではない
146: */
147: bool isPerfectNumber(const unsigned long n) {
148: unsigned long sum = 0;
149:
150: // 自分自身以外の約数の和を求める
151: for (unsigned long i = 1; i < n; ++i) {
152: if (n % i == 0) { // numがiで割り切れる場合
153: sum += i;
154: }
155: }
156:
157: // 和が元の数と等しければ完全数
158: return sum == n;
159: }
自分自身以外に約数をもつ 2 からはじめて、指定した範囲まで、1つずつユーザー関数 isPerfectNumber に渡し、完全数の定義に従っているかどうかを判定する。
isPerfectNumber の中では、エラトステネスの篩のような高速化アルゴリズムは使わず、総当たりで約数を求める。
5桁までの探索をやらせると、けっこう時間がかかる。しかも悲しいことに、冒頭の4つの完全数しか見つからない。5番目の完全数は 33550336 であり、これに到達するまでには相当な時間がかかるだろう。2024年10月12日発見された52個目の完全数は4102万4320桁の数字で、51番目のものより1600万桁以上大きくなっている。
解説：完全数の判定を高速化する
\( 1 \) と自分自身 \( n \) を除く約数の1つは、\( \sqrt{n} \) 以下であることは自明である。そして、その数とペアになる約数がある。
perfectNumber.cpp
161: /**
162: * 完全数かどうかを判定する（高速化）
163: * @param unsigned long n 判定する値
164: * @return bool TRUE:完全数である / FALSE:完全数ではない
165: */
166: bool isPerfectNumberRapid(unsigned long n) {
167: // 自分以外の約数をもたないので棄却
168: if (n < 2) {
169: return false;
170: }
171:
172: unsigned long sumDiv = 1; // 1はどの数の約数にも含まれる
173:
174: // 平方根までの約数を探し，ペアの約数を加える
175: unsigned long sqrtNum = sqrt(n);
176: for (unsigned long i = 2; i <= sqrtNum; ++i) {
177: if (n % i == 0) {
178: sumDiv += i; // 約数を加算
179: unsigned long pairDiv = n / i; // ペアの約数
180: if (pairDiv != i) { // ペアの約数を加算
181: sumDiv += pairDiv;
182: }
183: }
184: }
185:
186: // 和が元の数と等しければ完全数
187: return sumDiv == n;
188: }
こうすることで、計算量は多くても \( O(max) \times O(\sqrt{n}) \) に減少する。1～2桁の計算をしているときにはそれほど計算量は変わらないが、6桁（100万）になると、isPerfectNumber の計算量が \( O(1,000,000) \) であるのに比べ、isPerfectNumberRapid は \( O(1,000) \) と、3桁も減少する。つまり、桁数が増えれば増えるほど、計算速度の差が開く。
完全数を表示するユーザー関数 putPerfectNumberForce の第2引数は省略可能だが、1を代入すると、isPerfectNumberRapid を使って判定する。
解説：ユークリッド・オイラーの定理
じつは、偶数の完全数に限っては、18世紀の数学者レオンハルト・オイラーがユークリッド・オイラーの定理を発見しており、これを使うと計算回数を劇的に少なくすることができる。
ユークリッド・オイラーの定理によると、
\[ P = 2^{p - 1} \times (2^p - 1) \]
\( p \) が素数であり、なおかつ \( 2^p - 1 \) も素数である場合（これをメルセンヌ素数と呼ぶ）、\( P \) は偶数の完全数になる。
そして、2024年10月に発見された52個目まで、たまたま、すべて偶数の完全数だった。奇数の完全数が存在するかどうかは証明されていないのだが、少なくともパソコンのパワーでで52個まで計算するのは不可能だから、ユークリッド・オイラーの定理 を使って高速化させてもらう。
perfectNumber.cpp
215: /**
216: * メルセンヌ素数かどうかを判定する．
217: * @param unsigned int p 判定する指数
218: * @return bool TRUE:メルセンヌ素数である / FALSE:メルセンヌ素数ではない
219: */
220: bool isMersennePrime(unsigned int p) {
221: mpz_class mersenne = (mpz_class(1) << p) - 1; // 2^p - 1
222: return mpz_probab_prime_p(mersenne.get_mpz_t(), 25) > 0; // 確率的素数判定
223: }
perfectNumber.cpp
225: /**
226: * 完全数を生成する
227: * @param unsigned int p メルセンヌ指数
228: * @return mpz_class 完全数
229: */
230: mpz_class generatePerfectNumber(unsigned int p) {
231: mpz_class perfect = (mpz_class(1) << (p - 1)) * ((mpz_class(1) << p) - 1);
232: return perfect;
233: }
perfectNumber.cpp
235: /**
236: * 完全数を出力する（ユークリッド・オイラーの定理）
237: * @param unsigned long num 探索範囲の最大桁数
238: * @return なし
239: */
240: void putPerfectNumber(unsigned long num) {
241: mpz_class maxInteger;
242: mpz_ui_pow_ui(maxInteger.get_mpz_t(), 10, num);
243:
244: unsigned int index = 1;
245: unsigned long p = 2;
246: mpz_class perfectNumber = 0;
247: while (1) {
248: if (isMersennePrime(p)) {
249: perfectNumber = generatePerfectNumber(p);
250: // 計算終了
251: if (perfectNumber > maxInteger) {
252: break;
253: }
254: std::cout << index << ": " << perfectNumber << endl;
255: index++;
256: }
257: p++;
258: }
259: }
この方法では、計算量は \( O(log_2 \ max) \) となる。2桁（100）の時でも計算量が6に減少するし、6桁（100万）の時には19に激減する。
したがって、総当たり計算と同じ時間ではるかに大きな桁数の完全数を求めることができるので、完全数の型を unsigned long ではなく、GMPの mpz_class に変更し、事実上、無限大の完全数を求められるようにした。現行のノートPCでも、3000桁程度までであれば、数分で出力するだろう。
解説：コマンドラインオプションの定義と取得
perfectNumber.cpp
267: // コマンドライン・オプションの定義
268: options_description options("コマンドライン・オプション");
269: options.add_options()
270: ("number,n", value<unsigned long>(), "最大桁数")
271: ("force,f", "総当たり計算")
272: ("speed,s", "高速総当たり計算")
273: ("time,t", "計算時間表\示")
274: ("en,e", "英語表\示")
275: ("help,h", "ヘルプ")
276: ("version,v", "バージョン情報")
277: ;
278: // コマンドライン・オプションの取得
279: variables_map vm;
280: try {
281: store(parse_command_line(argc, argv, options), vm);
282: } catch(const boost::program_options::error_with_option_name& e) {
283: ErrorMessage = e.what();
284: cerr << ErrorMessage << endl;
285: return 1;
286: }
287: notify(vm);
オプションの定義は、options_description型によって行う。
parse_command_line関数が、options_description の定義にしたがってコマンドライン引数を解析し、その結果を variables_map オブジェクトに格納するよう指示する。notify関数を実行することで、はじめて variables_mapオブジェクトに解析結果が格納される。
perfectNumber.cpp
289: // 英語表示
290: if (vm.count("en")) {
291: flagEnglish = true;
292: }
293: // ヘルプ情報を表示する．
294: if (vm.count("help")) {
295: dispHelp(flagEnglish);
296: // バージョン情報
297: } else if (vm.count("version")) {
298: dispVersion(flagEnglish);
オプションの後に指定された値は、vm["オプション"].as<データ型>() のようにして取り出すことができる。
perfectNumber.cpp
299: // 完全数を求める
300: } else {
301: // 計算時間表示
302: if (vm.count("time")) {
303: flagTime = true;
304: }
305: // 最大桁数
306: unsigned long num = 100;
307: if (vm.count("number")) {
308: num = (unsigned long)vm["number"].as<unsigned long>();
309: }
310: // 計算開始時刻
311: clock_t t0 = clock();
312: // 総当たり計算
313: if (vm.count("force")) {
314: putPerfectNumberForce(num, 0);
315: // 高速総当たり計算
316: } else if (vm.count("speed")) {
317: putPerfectNumberForce(num, 1);
318: // ユークリッド・オイラーの定理
319: } else {
320: putPerfectNumber(num);
321: }
322: // 計算完了時刻
解説：計算量は非機能要件として検討する
結果を早く求めることができればユーザー喜ぶから、システムの非機能要件として計算量を減らすことを検討するといい。そして、前提条件を導入するかどうかはユーザーに諮らなければならないことだから、数学的に計算量 \( O \) を求め、どのくらい短縮できるかを数字をもって示すようにしよう。
参考サイト
- C++ 開発環境の準備：ぱふぅ家のホームページ
- PHPで完全数を求める
古代から 6, 28, 496, 8128 の4つが完全数であることが知られているが、ピタゴラスが名付けたとか、世界を創造した6日間と月の公転周期の28日が含まれているからキリスト教の神を完全性を表しているなどと言われてきた。
完全数を求める方程式は発見されていない。自然数を1つずつ虱潰しにしていかなければならないわけだが、こういうときに黙々と作業をするコンピュータが重宝する。
今回は、C++ で完全数を求めるプログラムを作るとともに、計算量について考える。
（2025年2月22日）使用ライブラリ更新