3

除数関数は、自然数の約数の合計です。

少し調べてみると、与えられた自然数Nの約数関数を見つけたい場合、これは非常に良い方法であることがわかったので、Pythonでコーディングしようとしました。

def divisor_function(n):
    "Returns the sum of divisors of n"
    checked = [False]*100000
    factors = prime_factors(n)
    sum_of_divisors = 1 # It's = 1 because it will be the result of a product
    for x in factors:
        if checked[x]:
            continue
        else:
            count = factors.count(x)
            tmp = (x**(count+1)-1)//(x-1)
            sum_of_divisors*=tmp
            checked[x]=True
    return sum_of_divisors

それはかなりうまく機能しますが、改善できると確信しています（例：要素を含むリストを作成します100000が、ほとんどの要素を使用していません）。

どのように改善/実装しますか？

PSこれはprime_factors：

def prime_factors(n):
    "Returns all the prime factors of a positive integer"
    factors = []
    d = 2
    while (n > 1):
        while (n%d==0):
            factors.append(d)
            n /= d
        d = d + 1
        if (d*d>n):
            if (n>1): factors.append(int(n));
            break;
    return factors
4

5 に答える 5

8

除数の合計を計算するときは、p 1 k 1 p 2 k 2 ...の形式でnを因数分解する必要があります。つまり、因数分解の各素数の指数が必要です。現時点では、素因数のフラットリストを計算し、指数を計算するために呼び出してこれを行っています。次のように、最初に必要な形式で素因数分解を簡単に生成できるため、これは時間の無駄です。 count

def factorization(n):
    """
    Generate the prime factorization of n in the form of pairs (p, k)
    where the prime p appears k times in the factorization.

    >>> list(factorization(1))
    []
    >>> list(factorization(24))
    [(2, 3), (3, 1)]
    >>> list(factorization(1001))
    [(7, 1), (11, 1), (13, 1)]
    """
    p = 1
    while p * p < n:
        p += 1
        k = 0
        while n % p == 0:
            k += 1
            n //= p
        if k:
            yield p, k
    if n != 1:
        yield n, 1

上記のコードに関する注意：

  1. このコードを変換して、リストを作成して（を繰り返し呼び出して）返すのではなく、因数分解を生成するappendようにしました。Pythonでは、シーケンス全体をメモリに保存しなくても、生成時に要素を1つずつ使用できるため、この変換はほとんどの場合改善されます。

  2. これは、doctestがうまく機能する種類の関数です。

これで、除数の合計の計算は非常に簡単です。チェックされた因子のセットを保存したり、各因子が発生した回数をカウントしたりする必要はありません。実際、1行で実行できます。

from operator import mul

def sum_of_divisors(n):
    """
    Return the sum of divisors of n.

    >>> sum_of_divisors(1)
    1
    >>> sum_of_divisors(33550336) // 2
    33550336
    """
    return reduce(mul, ((p**(k+1)-1) // (p-1) for p, k in factorization(n)), 1)
于 2013-01-16T14:50:23.877 に答える
1

2行だけ変更する必要があります。

def divisor_function(n):
    "Returns the sum of divisors of n"
    checked = {}
    factors = prime_factors(n)
    sum_of_divisors = 1 # It's = 1 because it will be the result of a product
    for x in factors:
        if checked.get(x,False):
            continue
        else:
            count = factors.count(x)
            tmp = (x**(count+1)-1)//(x-1)
            sum_of_divisors*=tmp
            checked[x]=True
    return sum_of_divisors
于 2013-01-16T13:58:16.260 に答える
1

なぜ昇順で因子を返すことが保証されているのにdict、またはset-またはcount()-を使用するのですか？あなたは前の要因prime_factors()だけに対処します。カウントは、反復の一部にすることができます。

def divisor_function(n):
    "Returns the sum of divisors of n"
    factors = prime_factors(n)
    sum_of_divisors = 1 
    count = 0; prev = 0;
    for x in factors:
        if x==prev:
            count += 1
        else:
            if prev: sum_of_divisors *= (prev**(count+1)-1)//(prev-1)
            count = 1; prev = x;
    if prev: sum_of_divisors *= (prev**(count+1)-1)//(prev-1)
    return sum_of_divisors
于 2013-01-17T08:12:47.677 に答える
1 
def sum_divisors(n):
    assert n > 0
    if n == 1:
        return 0
    sum = 1
    if n % 2 == 0:              # if n is even there is a need to go over even numbers
        i = 2
        while i < sqrt (n):
            if n % i == 0:
                sum = sum + i + (n//i)  # if i|n then n/i is an integer so we want to add it as well
            i = i + 1
        if type (sqrt (n)) == int:  # if sqrt(n)|n we would like to avoid adding it twice
            sum = sum + sqrt (n)
    else:
        i = 3
        while i < sqrt (n):     # this loop will only go over odd numbers since 2 is not a factor
            if n % i == 0:
                sum = sum + i + (n//i)  # if i|n then n/i is an integer so we want to add it as well
            i = i + 2
        if type (sqrt (n)) == int:  # if sqrt(n)|n we would like to avoid adding it twice
            sum = sum + sqrt (n)
    return sum
于 2014-11-13T12:54:40.667 に答える
0

これが私のJava番号ユーティリティ（Project Eulerで広く使用されている）で行うことです。

  • 明示的な指数を使用して素因数分解を生成します（Gareth Reesによる回答を参照）。

  • それに基づくさまざまな関数で素因数分解を展開します。つまり、素因数分解と同じアルゴリズムを使用しますが、因数と指数を格納する代わりに、必要な値を直接計算します。

  • デフォルトでは、テストは2と奇数の除数のみです。私には方法がfirstDivisor(n)ありnextDivisor(n,d)、そのために。

  • オプションで、範囲を下回るすべての数値の最小除数のテーブルを事前計算します。これは、境界より下のすべてまたはほとんどの数値を因数分解する必要がある場合に非常に役立ちます（速度が約向上しますsqrt(limit)）。firstDivisor(n)テーブルをandメソッドにフックするnextDivisor(n,d)ので、これによって因数分解アルゴリズムが変更されることはありません。

于 2013-01-18T08:20:21.150 に答える