欧拉整体:优化

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这样的库可以提供更快的分解例程。