4

Project Euler Problem 12 の次のコードがあります。ただし、実行に非常に時間がかかります。スピードアップするための提案はありますか？

n = input("Enter number: ")
def genfact(n):
    t = []
    for i in xrange(1, n+1):
        if n%i == 0:
            t.append(i)
    return t

print "Numbers of divisors: ", len(genfact(n))
print

m = input("Enter the number of triangle numbers to check: ")
print
for i in xrange (2, m+2):
    a = sum(xrange(i))
    b = len(genfact(a))
    if b > 500:
        print a

n には 6 などの任意の数値を入力して、因数の数のリストの長さが実際に返されるかどうかを確認します。m には、80 000 000 と入力します。

少数の場合は比較的迅速に機能します。私が入力した場合b > 50; a に対して 28 を返しますが、これは正しいです。

4

5 に答える 5

4

ここでの私の答えは、きれいでもエレガントでもありません。それでも力ずくです。しかし、問題空間を少し単純化し、10 秒以内に正常に終了します。

n の因数を取得する: @usethedeathstar が述べたように、最大​​ までの因数をテストすることができn/2ます。ただし、n の平方根までのみをテストすることで、より良い結果が得られます。

let n = 36
=> factors(n) : (1x36, 2x18, 3x12, 4x9, 6x6, 9x4, 12x3, 18x2, 36x1)

ご覧のとおり、6 (36 の平方根) の後でループします。また、要素を明示的に返す必要はありません。要素がいくつあるかを調べるだけです...したがって、sum() 内のジェネレーターでそれらを数えるだけです。

import math

def get_factors(n):
    return sum(2 for i in range(1, round(math.sqrt(n)+1)) if not n % i)

三角数のテスト

ジェネレーター関数を使用して三角数を生成しました。

def generate_triangles(limit):
    l = 1
    while l <= limit:
        yield sum(range(l + 1))
        l += 1

最後に、テストを開始します。

def test_triangles():
    triangles = generate_triangles(100000)
    for i in triangles:
        if get_factors(i) > 499:
            return i

これをプロファイラーで実行すると、10 秒以内に完了します。

$ python3 -m cProfile euler12.py 

361986 function calls in 8.006 seconds

ここでの最大の時間節約はget_factors(n)、n の平方根までしかテストしないことです。これにより、非常に高速になり、因子のリストを生成しないことで大量のメモリ オーバーヘッドを節約できます。

私が言ったように、それはまだきれいではありません - もっとエレガントな解決策があると確信しています。しかし、それはより高速であるという法案に適合します:)

于 2013-07-19T11:41:09.107 に答える