Q&A
Closed
完全数を求めたいです。真なら整数の約数を出力し、偽なら0を出力するという仕組みです。
Traceback (most recent call last):
File "D:/python/gomi.py", line 5, in <module>
for j in i:
TypeError: 'int' object is not iterable
a = int(input())
#約数
for i in range(1,a):
if a % i == 0:
for j in i:
b = sum(j)
if b == a:
print(j)
else:
print("0")
整数aの約数は得られました。
そこから約数をリストjに変換して、sum関数で合計を求めたいです。
が、intオブジェクトが繰り返し不可と出てしまい詰んでいます。
助けてほしいです。。。
jをリストで定義しておき、約数であればリストに追加するという形で求めている処理になるかと思います。
a = int(input())
j = []
for i in range(1, a):
if a % i == 0:
j.append(i)
b = sum(j)
if b == a:
print(j)
else:
print("0")
@mt___sugi
Questioner
問題が「約数全ての列挙」であれば，整数aの約数にはa自身も含むはずです．が，上のコードでは約数リストにはa自身を含みません1．なので，このリストに追加で最後の出力ではaも出力してあげる必要があると思いました．
a = int(input())
divisor = list()
for i in range(1, a):
if a % i == 0:
divisor.append(i)
if a == sum(divisor):
print(divisor, a) # 最後にaも一緒に出力する
else:
print(0)
ただ，この書き方だと出力が以下のようになって
[1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064] 8128
少し変なので，range(1, a)だったのをrange(1, a + 1)にすることで約数全てを求めるようにしたうえで条件文2を変更して
a = int(input())
divisor = list()
for i in range(1, a + 1): # 1からa + 1未満まで求める
if a % i == 0:
divisor.append(i)
if a * 2 == sum(divisor): # 条件文の変更
print(divisor)
else:
print(0)
とすればきれいに出力されると思います．また，listの標準出力についてくる角括弧も省いた上でPythonicな書き方で
a = int(input())
divisor = [i for i in range(1, a + 1) if a % i == 0]
print(', '.join(map(lambda x: str(x), divisor)) if a * 2 == sum(divisor) else 0)
と書くのもありだと思います．また，時間計算量の観点から上のコードでは整数$N$に対して$O(N)$の実行時間がかかるコードになっており，約数を求めるアルゴリズムの中では低速なものが実装されています．$O(\sqrt{N})$にまで計算量を削減して
divisor = list()
for i in range(1, a):
if i * i > a:
break
if a % i == 0:
divisor.append(i) # iで割り切れたら約数
if i * i != a:
divisor.append(a // i) # そのときaをiで割った商も約数
と書くこともできます．こちらで試したそれぞれの約数列挙の実行時間は
| 数 | 完全数 | $O(N)$なコード | $O(\sqrt{N})$なコード |
|---|---|---|---|
| 8128 | Yes | $191$$[\mu{\rm s}]$ | $5.38$$[\mu{\rm s}]$ |
| 123456 | No | $3.21$$[{\rm ms}]$ | $0.02$$[{\rm ms}]$ |
| 33550336 | Yes | $ 842$$[{\rm ms}]$ | $0.26$$[{\rm ms}]$ |
| 123456789 | No | $3.23$$[{\rm s}]$ | $0.0005$$[{\rm s}]$ |
| 8589869056 | Yes | $750$$[{\rm s}]$ | $0.007$$[{\rm s}]$ |
| 137438691328 | Yes | 多分半日ぐらい(予測) | $0.032$$[{\rm s}]$ |
| 2305843008139952128 | Yes | 数千～数万年(予測) | $150$$[{\rm s}]$ |
になります．判定させる値にもよりますが，実行時間が短いに越したことはありません．参考までに．
for i in range(1, a)では1からa未満までのループなので取り扱われる数字は1からa - 1までです．数aに対してif a % i == 0という約数であるかの判定が行われません． ↩
Wikipedia-完全数でも「完全数の定義は、正の約数の総和が自分自身の2倍に等しいことと同値である。すなわち、$N$が完全数であるとは、約数関数$\sigma(\cdot)$に対して$\sigma(N)=2N$が成り立つことであると表現できる。」と書いてあるので，変更した条件文の方が完全数の定義に沿っています． ↩
@mt___sugi
Questioner
@mt___sugi
Questioner