12

オイラーの totient 関数を計算する効率的な方法を見つけようとしています。

このコードの何が問題になっていますか? 機能していないようです。

def isPrime(a):
    return not ( a < 2 or any(a % i == 0 for i in range(2, int(a ** 0.5) + 1)))

def phi(n):
    y = 1
    for i in range(2,n+1):
        if isPrime(i) is True and n % i  == 0 is True:
            y = y * (1 - 1/i)
        else:
            continue
    return int(y)
4

9 に答える 9

5

あなたは3つの異なる問題を抱えています...

  1. ynではなく、初期値として等しい必要があります1
  2. コメントで言及されているように、整数除算は使用しないでください
  3. n % i == 0 is TruePython が比較を連鎖させているため、あなたが思っていることをしていません! n % i等しい場合でも、0それ0 == 0はTrue しかし 0 is TrueですFalse! Trueとにかく必要ではないので、括弧を使用するか、単に比較を取り除きます。

それらの問題を解決し、

def phi(n):
    y = n
    for i in range(2,n+1):
        if isPrime(i) and n % i == 0:
            y *= 1 - 1.0/i
    return int(y)
于 2013-08-07T21:41:49.520 に答える
2

これはorlpの答えのより短い実装です。

from math import gcd
def phi(n): return sum([gcd(n, k)==1 for k in range(1, n+1)])

他の人がすでに述べたように、パフォーマンスの最適化の余地があります。

于 2020-09-30T06:21:43.663 に答える
1

実際に phi を計算するには (任意の数は n とします) 、p が n の素因数である式
を使用します。

したがって、コードにはいくつかの間違いがあります:
1.は 2yに等しい必要があります。実際にはと両方とも整数であるため、それらの評価も整数になるため、間違った結果につながります。n
1/i1i

必要な修正を加えたコードを次に示します。

デフォルト ファイ(n):
    y = n
    範囲 (2,n+1) の i の場合:
        isPrime(i) と n % i == 0 の場合:
            y -= y/i
        そうしないと：
            継続する
    int(y) を返す
于 2016-06-25T11:33:13.137 に答える