c - (C)中分母为d的缩减分数的数量

我整整工作了一天。
好吧，我的代码现在可以正常工作了；

但是我需要减少执行此代码所需的时间，以及另一个问题，该代码不适用于大
像长d的数字= 9999999999;

所以我希望有人能帮助我解决这个问题
顺便说一下，这就是我正在做的挑战；

https://www.codewars.com/kata/number-of-proper-fractions-with-denominator-d/train/c

我正在尝试使用ma代码中所示的Euler的Totient公式解决该问题；
在这里您可以了解Euler的Totient的工作原理。

https://www.dcode.fr/euler-totient

提前谢谢。

int is_prime(long num)
{
  long i = 2;
  if (num == 1) return 0;

  for (i; num >= i * i; i++)
      if (num % i == 0) return 0;
  return (1);
}

long properFractions(long d)
{
  long sum = 0;
  long i = 2;
  long double v1 = 1.0;
  long keep = d;

  for (i; i <= d; i++)
      if(d % i == 0 )
         if (is_prime(i))
             v1 *= (1.0 - (1.0 / i));

  if (keep != 1)
     sum = (keep * v1);
  return (sum);
}

最佳答案

您需要找到小于n的互质数。

n = p1^x1 * p2^x2 * ... * pn^xn
phi(n) = p1^(x1-1)*(p1-1) * p2^(x2-1)*(p2-1) * ... * pn^(xn-1)(pn-1)

现在，即使寻找一个很大的数字，也可以得到最多的素数，最多可以迭代sqrt(n)个数字。一旦执行，将使用功率计算（在O(logt)情况下为a^t）。这将为您获取一份AC。

关于c - (C)中分母为d的缩减分数的数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53357627/