c - 欧拉 Totient : Optimization

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。这应该可以将时间缩短一半。