Project Euler 021を解いてみる。「友愛数」

Project Euler 021

021

d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )
もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.
例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.
また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.
それでは10000未満の友愛数の和を求めよ.

->次の問題

考え方

10000未満の自然数をループで回し、
約数の合計を計算→その値からまた約数の合計を計算し、元の数と一致するかを判定します。

コード

euler021.py

def main():
    n = 10000
    amicable_numbers = [i if is_amicable_number(i) else 0 for i in range(1, n)]
    print(sum(amicable_numbers))


def is_amicable_number(n: int) -> bool:
    """友愛数か否かを判定する関数
    Args:
        n: 自然数
    Returns:
        bool: 友愛数ならTrue
    """
    pair_num = sum(get_divisors(n)) # nの約数の和をpair_numとする
    if n == pair_num:  # 完全数を除去
        return False
    return n == sum(get_divisors(pair_num))  # pair_numの約数の和がnなら友愛数


def get_divisors(n: int) -> list:
    """真の約数(n以外の約数)を返す関数
    Args:
        n: 自然数
    Returns:
        list: 約数のリスト
    """
    divisors = [1,]
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            temp_divisor = n // i
            if  temp_divisor != i:
                divisors.append(temp_divisor)
    return divisors

if __name__ == '__main__':
    from time import time as t
    st = t()
    main()
    print(t() - st, 'sec')

paizaにて実行
結果 31626 0.06382584571838379 sec
ちなみに友愛数は
[220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]
の10個です。

問題点

この方法では1~9999の数値それぞれについて判定を行っているので、220で判定を行ったあとにペアである284でももう一度判定を行っており、無駄がありそうです。

改良

ある数字が友愛数で合った場合、ペアとなる数字も同時にリストに登録するようにします。

コード

euler021.py

def main():
    n = 10000
    amicable_numbers = []
    for i in range(1, n):
        pair_num = sum(get_divisors(i))
        # 2つの数字ペアi,pair_numをi < pair_numとすることで
        # 完全数の場合と入れ替わりのパターンを排除
        if pair_num > i & i == sum(get_divisors(pair_num)):
                amicable_numbers += [i, pair_num]
    print(amicable_numbers)
    print(sum(amicable_numbers))

• 友愛数判定の関数は使わずにmain内で処理するように変更
• ペアの友愛数を同時にリストに追加

結果 31626 0.04690241813659668 sec
25%ほど早くなりましたが、10000未満の友愛数のペアはもともと5組しかないのでアルゴリズムの効率化というよりは関数呼び出しが減ったことの影響な気がします(；・∀・)