プロジェクトオイラー23
プロジェクトオイラーの問題23をPython3で解きました。
問題
Problem 23 - Project Euler
問題は、2つの過剰数(自身を除く約数の和が、自分自身より大きい自然数のこと)の和で書き表すことのできない自然数の総和を求めなさいというものでした。ヒントとして、28124以上の全ての自然数は2つの過剰数の和で表されることが与えられていました。そこで、28123以下の自然数で、2つの過剰数の和で表せない自然数をリスト化し、総和をとるプログラムを書きました。
import time start = time.time() def divs_sum(S): '''約数の和(自分自身は除く)''' s = 1 for i in range(2, int(S**0.5 + 1)): if S % i == 0: s += i + int(S / i) if S**0.5 == int(S**0.5): s -= int(S**0.5) return s def abundant(N): '''Nが過剰数かどうか''' if divs_sum(N) > N: return 1 else: return 0 ab = [n for n in range(12, 28112) if abundant(n)] '''28111以下の番号で過剰数のものを格納''' l = [0] + [1] * 28123 '''0-28123までのリストを用意''' for i in ab: '''2つの過剰和で書ける整数のl-リスト番号は0にする''' for j in [num for num in ab if num >= i]: if i+j < 28124: l[i+j] = 0 s = 0 for i in range(28124): '''2つの過剰和で書けなかった整数を足していく''' if l[i]: s += i print(s) print(time.time()-start)
計算時間は酷い有様でした。