c - Euler Totient：优化

Question

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 代码。该程序似乎运行良好，但仍然很慢。请问我怎样才能让它更快？

Answer 1

首先检查div=2.

之后，您只需要检查奇数，因此您可以使用div += 2. 那应该把时间减半。

Answer 2

我不确定是否有更好的算法，但我们可以从容易实现的目标开始：您正在测试所有数字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 这样的库可以提供更快的因式分解例程。