⛳
Pythonで完全数かどうか判定する。
問題はこちらです。
完全数とは、ざっくりいうと、約数の和が自身の2倍になるような数のことです。
例えば、28の場合は以下のようになります。
28 * 2 = 1 + 2 + 4 + 7 + 14 + 28
じゃあ与えられた数字が完全数かどうか判定してみます。
解き方はいくつかありますが、まずは愚直に解いてみます。
これが愚直かはさておいてこのコードではパスできません。
このように非常に大きな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の関係も見えてくるからです。
ただしこちらは不要です。
で、正しい解答コードはこちらです。
数学何も覚えてない。。。
Discussion