Pythonで素敵な数字を見つける最も効率的な方法は何ですか？

Question

私は10000以下友愛数の合計を計算するためにPythonでコードを書いた：

def amicable(a, b): 
    total = 0 
    result = 0 
    for i in range(1, a): 
     if a % i == 0: 
     total += i 
    for j in range(1, b): 
     if b % j == 0: 
     result += j 
    if total == b and result == a: 
     return True 
    return False 

sum_of_amicables = 0 
for m in range (1, 10001): 
    for n in range (1, 10001): 
     if amicable(m, n) == True and m != n: 
      sum_of_amicables = sum_of_amicables + m + n 

コードは、Python 2.7.11で20分以上を実行しています。大丈夫ですか？どうすれば改善できますか？

Answer 1

コードを分割して、かなりの時間を費やしているコード部分を改善できます。

の1-

あなたはif m != n and amicable(m, n) == True:とif amicable(m, n) == True and m != n:を交換した場合、それはあなたのm != nがfalseされるために友好的な方法（最も高価なメソッド）に10000回のコールを保存します。

amicableメソッドでは、両方の数値のすべての要素を見つけるために1からnをループしています。要因を見つけるにはより良いアルゴリズムが必要です。あなたは上記のhereを使用することができます。ファクタを見つけるためにO(n)の複雑さがO(sqrt(n))に減少します。この最終的なコードは、あなたが言及した半分の時間である、私のために実行するために10分を取っ考慮すると、両方のあなたのコード上のポイントが

def amicable(a, b): 
    if sum(factors(a) - {a}) == b and sum(factors(b) - {b}) == a: 
     return True 
    return False 

sum_of_amicables = 0 
for m in range (1, 10001): 
    for n in range (1, 10001): 
     if m!= n and amicable(m, n) == True: 
      sum_of_amicables = sum_of_amicables + m + n 

なります

def factors(n):  
    return set(reduce(list.__add__, 
       ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) 

。

---

Iはfactors方法を最適化することによって一時30分にそれを最適化するようにさらにできました。

factorsメソッドに10000 * 10000コールがあります。そして、数字のそれぞれについて、factorsが10000回呼び出されます。つまり、同じ数に対して10000回の係数を計算します。したがって、コールごとに計算するのではなく、以前の要因計算の結果をキャッシュすることで最適化することができます。

factorsを変更して結果をキャッシュする方法は次のとおりです。

def factors(n, cache={}): 
    if cache.get(n) is not None: 
      return cache[n] 
    cache[n] = set(reduce(list.__add__, 
        ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) 
    return cache[n] 

全コード：（ランタイム午前1時30分）

だから、完全かつ最終的なコードは、あなたはまだそれをさらに向上させることができます

def factors(n, cache={}): 
    if cache.get(n) is not None: 
      return cache[n] 
    cache[n] = set(reduce(list.__add__, 
        ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) 
    return cache[n] 

def amicable(a, b): 
    if sum(factors(a) - {a}) == b and sum(factors(b) - {b}) == a: 
     return True 
    return False 

sum_of_amicables = 0 
for m in range (1, 10001): 
    for n in range (1, 10001): 
     if m!= n and amicable(m, n) == True: 
      sum_of_amicables = sum_of_amicables + m + n 

---

になります。

ヒント：sumは、それぞれの数値に対して10000回とも呼ばれます。

Answer 2

ダブルループは必要ありません。 Mを1から10000にループするだけで、 は各Mを因数分解し、除数の総和S（M）を計算します。次に、N = S（M）-Mが同じ除数の合計を有することを確認する。これは、親和性のある対の定義から導かれた単純なアルゴリズムである。

友好的なペアの検索を最適化するためには、さらに多くのトリックがあります。ほんの数分の1秒で、1,000,000,000以下の素敵な数を見つけることができます。 this in-depth articleを読むと、その記事の参照C++ codeも確認できます。 Oに最適化された

Answer 3

（N）

def sum_factors(n): 
    result = [] 
    for i in xrange(1, int(n**0.5) + 1): 
     if n % i == 0: 
      result.extend([i, n//i]) 
    return sum(set(result)-set([n])) 

def amicable_pair(number): 
    result = [] 
    for x in xrange(1,number+1): 
     y = sum_factors(x) 
     if sum_factors(y) == x and x != y: 
      result.append(tuple(sorted((x,y)))) 
    return set(result) 

実行それ

start = time.time() 
print (amicable_pair(10000)) 
print time.time()-start 

結果

set([(2620, 2924), (220, 284), (6232, 6368), (1184, 1210), (5020, 5564)]) 
0.180204153061 

は答えに追加するMacBook Proの

Answer 4

にわずか0.2秒かかります。

def sum_factors(self, n): 
    s = 1 
    for i in range(2, int(math.sqrt(n))+1): 
     if n % i == 0: 
      s += i 
      s += n/i 
    return s 

def amicable_pair(self, number): 
    result = 0 
    for x in range(1,number+1): 
     y = self.sum_factors(x) 
     if self.sum_factors(y) == x and x != y: 
      result += x 
    return result 

セットや配列は不要です。ストレージと明快さの向上。