1 
int main(void)
{
  int n, div, a, b;
  double phi;
  printf("Enter n:\n");
  if (scanf("%d", &n) < 1 || n <= 0)
  {
    printf("Wrong input.\n");
    return 1;
  }

  a = n;
  div = 2;
  phi = n;

  while (n != 1)
  {
    if (n % div != 0)
      div++;
    else
    {
      n = n / div;
      if (b != div)
      {
        b = div;
        phi = phi * (1.0 - 1.0 / div);
      }
    }
  }

  printf("phi(%d) = %.f\n", a, phi);

  return 0;
}

これは、学校の課題として作成した Eulers Totient のコードです。プログラムは正常に動作しているように見えますが、まだ遅いです。どうすれば速くなりますか？

4

2 に答える 2

1

を最初に確認しdiv=2ます。

あとは奇数をチェックするだけなので、 を使えますdiv += 2。これで時間は半減するはずです。

于 2013-11-01T13:00:59.340 に答える
0

より良いアルゴリズムがあるかどうかはわかりませんが、簡単に達成できることから始めることができます: までのすべての数値をテストしnて、その約数を見つけます。φ(n) の定義から、素因数のみが必要であることがわかっているため、これは冗長です。

すばらしい、線形探索を超多項式問題に変えただけだと言う人もいるかもしれません。

必ずしも。

P6 素数候補生成器を使用します。

def P6():
    yield 2
    yield 3
    i = 5
    while True:
        yield i
        if i % 6 == 1:
            i += 2
        i += 2

その上に因数分解関数を作成しましょう。

def factors(n):
    d = {}
    primes = p6()
    for p in primes:
        while n % p == 0:
            n /= p
            d[p] = d.setdefault(p, 0) + 1
        if n == 1:
            return d

これで φ(n) を見つけるのは簡単です。これを C で実装してみて、違いを測定してください。高速化が必要な場合は、GMP などのライブラリを使用すると、はるかに高速な因数分解ルーチンを提供できます。

于 2013-11-01T13:37:31.837 に答える