3

私は、与えられた自然数のすべての除数を見つけてそれらをリストとして返す次の関数を書きました。

def FindAllDivisors(x):
    divList = []
    y = 1
    while y <= math.sqrt(x):
        if x % y == 0:
            divList.append(y)
            divList.append(int(x / y))
        y += 1
    return divList

入力が18桁の数字である場合は非常に遅いことを除いて、これは非常にうまく機能します。どうすればスピードアップできるかについて何か提案はありますか？

更新：

フェルマーの小定理に基づいて素数性をチェックする方法は次のとおりです。

def CheckIfProbablyPrime(x):
    return (2 << x - 2) % x == 1

この方法は、単一の数値をチェックするときに非常に効率的ですが、特定の境界まですべての素数をコンパイルするためにこの方法を使用する必要があるかどうかはわかりません。

4

4 に答える 4

25

素因数分解を計算することにより、数値のすべての除数を見つけることができます。各除数は、因数分解の素数の組み合わせである必要があります。

素数のリストがある場合、これは因数分解を取得する簡単な方法です。

def factorize(n, primes):
    factors = []
    for p in primes:
        if p*p > n: break
        i = 0
        while n % p == 0:
            n //= p
            i+=1
        if i > 0:
            factors.append((p, i));
    if n > 1: factors.append((n, 1))

    return factors

これは試行割り算と呼ばれます。これを行うには、はるかに効率的な方法があります。概要については、こちらをご覧ください。

除数の計算は非常に簡単になりました。

def divisors(factors):
    div = [1]
    for (p, r) in factors:
        div = [d * p**e for d in div for e in range(r + 1)]
    return div

すべての除数を計算する効率は、素数を見つけるためのアルゴリズム（ここでは小さな概要）と因数分解アルゴリズムに依存します。後者は非常に大きな数の場合は常に低速であり、それについてできることはあまりありません。

于 2012-09-14T09:47:10.617 に答える
3

math.sqrt(x)結果を別の変数に保存してから、それと照合することをお勧めしyます。whileそれ以外の場合は、の各ステップで再計算され、math.sqrt軽量の操作ではありません。

于 2012-09-14T09:44:41.940 に答える
1

素因数分解を行い、その結果からすべての除数を計算します。

于 2012-09-14T09:48:20.397 に答える
0

パフォーマンスのヒットが多いかどうかはわかりませんが、intへのキャストは不要だと確信しています。少なくともPython2.7ではint x / int y、intを返します。

于 2012-09-14T09:48:26.167 に答える