Perfect Number
nの真の約数とは、n自身より小さい正の約数です。完全数は、その真の約数の和に等しい数です。例：6 = 1 + 2 + 3。正の整数nが与えられます。nが完全数ならtrueを、そうでなければfalseを返してください。
関数
- ninteger
- テストする正の整数
- 戻り値boolean
- n が真の約数の和に等しい場合は真、そうでなければ偽
制約
1 ≤ n ≤ 108
例
- 入力
- n = 28
- 出力
- true
- 説明
28の真の約数は1、2、4、7、14です。それらを合計すると28になるので、28は完全数です。
- 入力
- n = 12
- 出力
- false
- 説明
12の真の約数は1、2、3、4、6です。それらを合計すると16になり、12を上回ります。
- 入力
- n = 1
- 出力
- false
- 説明
1には真の約数がまったくないため、合計は1ではなく0です。
提出時に隠しテスト+16件
発展問題
すべての偶数の完全数は、2^(p-1) × (2^p-1)という形をしており、2^p-1は素数です。各数を個別に調べずに、この公式を使って10^8未満の完全数をすべて列挙できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
28の真の約数を書き出してください。5以下の数だけを調べた場合、どの約数が見つかりますか？約数はペアになります。
dがnを割り切るなら、n / dも割り切ります。各ペアの一方は√n以下です。合計を
1から始め、n == 1の場合はfalseを返し、d * d ≤ nの間、dを2から順にループします。dとn / dを加えますが、両者が等しい場合は1回だけ加えます。
解説
定義では約数の和を求めます。単純なループでは、n / 2までの候補をすべて試します。n = 10^8の場合、これは5 × 10^7回の除算になります。約数は積がnになるペアなので、√n（約10^4ステップ）までだけ調べながら、各ペアの両方の要素を集めることができます。
すべての真の約数を足す
正しいが、最大のテストでは終わらない
考え方
定義に従います。1から順にdを試し、n % d == 0のときは、累計にdを加えます。最後に累計をnと比較します。28の場合、ループで見つかるのは1、2、4、7、14で、1 + 2 + 4 + 7 + 14 = 28となります。
n / 2で止められます。n以外の約数で割ると商は少なくとも2になるため、その約数がnの半分を超えることはありません。この上限はn = 1の場合にも対応します。ループは0回実行され、累計は0のままで、答えはfalseです。
範囲を半分にしても、増加の度合いは変わりません。n = 10^8の場合、ループは依然として5 × 10^7回実行され、約数かどうかにかかわらず、そのサイズの入力すべてで同じ回数実行されます。
アルゴリズム
totalを0に設定します。dを1からn / 2までループします。n % d == 0の場合、dをtotalに加えます。total == nかどうかを返します。
def isPerfect(n):
total = 0
# No proper divisor of n is larger than n / 2.
for d in range(1, n // 2 + 1):
if n % d == 0:
total += d
return total == n平方根までの約数のペアを集める
考え方
d가 n을 나누면 n / d도 n을 나눕니다. 28의 경우 쌍은 1 × 28, 2 × 14, 4 × 7입니다. 각 쌍에서 한 수는 √n 이하입니다. 두 수가 모두 √n보다 크면 곱이 n보다 커지기 때문입니다. 따라서 √n까지 탐색하면 각 쌍을 한 번씩 만나게 되고, 진행하면서 두 수를 모두 더하면 됩니다.
두 수는 주의가 필요합니다. 1 × n 쌍에는 n 자체가 포함되는데, 이는 진약수가 아닙니다. 따라서 합계는 1에서 시작하고 탐색은 2에서 시작하세요. 하지만 n = 1일 때는 이 시작값이 맞지 않습니다. 약수가 자기 자신뿐이므로, 먼저 false를 반환하세요. 그리고 n이 제곱수이면 제곱근은 자기 자신과 짝을 이룹니다. 36의 경우 6 × 6은 6을 두 번이 아니라 한 번 더해야 합니다.
上限は d * d ≤ n と書きます。これなら整数のまま扱えます。n = 10^8 の場合、ループは d = 10^4 で停止するため、5 × 10^7 回ではなく、約 10^4 回実行されます。
アルゴリズム
n == 1の場合、falseを返します。totalを1に、dを2に設定します。d * d ≤ nの間、dがnを割り切る場合はdを加算し、n / dがdと異なる場合はそれも加算します。- 次の
dに進みます。 total == nかどうかを返します。
def isPerfect(n):
if n == 1:
return False
total = 1 # 1 divides every n > 1; n itself does not count
d = 2
while d * d <= n:
if n % d == 0:
total += d
partner = n // d
if partner != d: # a square root pairs with itself: add it once
total += partner
d += 1
return total == n
落とし穴と境界ケース
約数を組にして数える方法は簡潔で、そのバグはどれも合計を約数1つ分だけ変えます。
n自身を数えてしまう。1 × nの組はnを加算するため、すべての数の合計がnを上回るように見えてしまいます。合計は1から始め、探索は2から始めましょう。1を完全数と判定してしまう。合計を1から始めると、入力1は1 == 1と比較されます。真の約数の合計は0なので、ループの前に処理しましょう。- 平方根を2回加算してしまう。
16の真の約数は1、2、4、8で、合計は15です。4を2回加算すると19になります。 d * d < nで終了してしまう。平方根が完全に飛ばされるため、16の4は一度も数えられません。- 浮動小数点の平方根から上限を求めてしまう。単精度の場合、または倍精度で
2^53を超える場合、完全平方数の平方根が1だけ小さくなり、約数を見落とすことがあります。d * d ≤ nの判定は整数のまま行うため、この問題は起こりません。
よくある質問4
完全数かどうかを確認する時間計算量はどれくらいですか？
√n までの約数のペアを集めるには、時間が O(√n)、空間が O(1) 必要です。n = 10^8 の場合、これは約 10^4 ステップです。n / 2 までの候補をすべて調べると O(n) となり、同じ入力では約 5 × 10^7 ステップです。
10^8未満の完全数はいくつありますか？
5つです：6、28、496、8128、33550336。すぐに数が少なくなります。次の数である8589869056は、32ビット整数にも収まりません。
奇数の完全数は存在するのでしょうか？
誰にも分かっていません。これまでに見つかった完全数はすべて偶数です。10^1500未満の奇数の完全数は探索によってすべて除外されていますが、奇数の完全数が存在し得ないことを示す証明はありません。入力が偶数だという推測ではなく、定義に基づいて関数を動作させる必要があります。
完全数、過剰数、不足数の違いは何ですか？
真の約数の合計をその数と比較します。同じなら完全数です。たとえば 28 です。大きければ過剰数です。たとえば 12 は約数の合計が 16 です。小さければ不足数です。真の約数が 1 だけであるすべての素数がその例です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isPerfect(n):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
n = 28
期待値
true