Pythonで完全数かどうか判定する。

2023/01/25に公開約800字

問題はこちらです。

完全数とは、ざっくりいうと、約数の和が自身の2倍になるような数のことです。

例えば、28の場合は以下のようになります。

28 * 2 = 1 + 2 + 4 + 7 + 14 + 28

じゃあ与えられた数字が完全数かどうか判定してみます。
解き方はいくつかありますが、まずは愚直に解いてみます。
https://github.com/Runacy/public-anything/blob/main/algorythm/Perfect_number_bad_sol1.py

これが愚直かはさておいてこのコードではパスできません。

このように非常に大きなnumの場合、Time Limit Exceededします。

じゃあどうやって解けばいいのかというと、次のように考えます。

28 = 1 + (2 + 28 / 2) + (4 + 28 / 4)
   = 1 + 2 + 14 + 4 + 7

のように考えます。

要するに、約数をiとして、28をnとしたときに、i + n/iの関係が見えてきます。
さらに、この場合、iは28の平方根になります。
これが28 * 0.5では不十分なのは、n/i + iの関係も見えてくるからです。
ただしこちらは不要です。

で、正しい解答コードはこちらです。
https://github.com/Runacy/public-anything/blob/main/algorythm/Perfect_number.py

数学何も覚えてない。。。

Discussion

ログインするとコメントできます