チャレンジ #274: 完全数

[AYXAcademy]

こんにちは、Maveryx！

 先週の課題の解決策はここで見つけることができます

このチャレンジは、最もクリエイティブなチャレンジ貢献者の 1 人であるIppei Nakagawaによって提出されました。 @gawa さん、貴重な貢献に感謝します。また、Inspire2024 中に直接お会いできて嬉しかったです!

完璧な人は神話かもしれませんが、完全な数は現実のものです。完全数とは、(それ自体を除く) 約数の合計に等しい正の整数です。

あなたの課題は、入力データに与えられた1 ～ 10,000 の範囲の整数のリストから、その中に隠されている完全数を特定することです。たとえば、最小の完全数は 6 で、これは6の約数 1、2、3 の合計です。

復習が必要ですか?アカデミーでこのレッスンを復習して準備を整えてください。

・データの集計

健闘を祈ります！

[Qiu]

できました。

スポイラ

[DaisukeTsuchiya]

@gawa さん、採用おめでとうございます。

スポイラ

[KosukeUchihashi]

私の回答です。

Num以下の数を列挙するという愚直な方法を使ったのでもう少しNumが多くなると動かなくなりそうなWorkflowです。

メルセンヌ素数というものを使えばもう少し処理を軽くできそうな気がします。

[gawa]

@KosukeUchihashi  挑戦ありがとうございます。ネタバレに、計算量を減らすロジックを書きます

スポイラ

整数Xの約数は、必ず　[X/2]　以下なので、行生成のループ条件を以下にすることで、約数候補の探索総数を約半分に減らせます。
私の環境では4.5秒➡3.0秒まで短縮できました

[SuguruYoshinaga]

できました。

スポイラ

[AkimasaKajitani]

できました！

スポイラ

 

@gawa さん採用おめでとうございます！

[Yoshiro_Fujimori]

やはり brute force しか思いつきませんでした。

なお、8,127の次の完全数は33,550,336だとWikipediaで聞いたので、

同じ処理で出せるか試してみたところ、30分経過時点で 125,696 までしか進まないので止めました。。

スポイラ

Workflow

[AkimasaKajitani]

@Yoshiro_Fujimori さん　その発想はAoCの１日の後半の問題みたいですね！

[gawa]

偶数の完全数の性質を使うと、次の完全数は比較的簡単に求められます。スポイラーにネタバレを書いておきます。

https://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E6%95%B0

スポイラ

Wikipediによると、「6以外の完全数は、1から連続する正の奇数の立方和で表せる」そうなので、天下りになりますが、検索対象をかなり制限することができます。