Количество сокращенных дробей со знаменателем d в (С)

Question

Я работаю над этим ката целый день. хорошо мой код работает сейчас хорошо;

но мне нужно сократить время, которое требуется для выполнения этого кода, и другую проблему, с которой этот код не работает числа типа long d = 9999999999 ;

так что я хочу, чтобы кто-то помог мне с этой проблемой кстати, это проблема, которую я делаю;

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

и я пытаюсь решить ее с помощью формулы Эйлера , как показано в коде ma; здесь вы можете понять, как работает 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);
}

Answer 1

код не работает с большими числами, такими как long d = 9999999999;

Это связано с двумя причинами: недостаточный диапазон должен long быть 32-битным и long*longпереполнение.

1. Чтобы работать со значениями, такими как 9,999,999,999 (34-битное значение), обязательно используйте 34+-битную математику.Предложите unsigned long long, который по крайней мере 64-битный.

2. Избегайте теста num >= i * i, так как i*i может легко переполниться.Используйте num/i >= i. ¹

Вместо:

int is_prime(unsigned long long num) {
  if (num <= 1) return 0;// Handle 0,1

  unsigned long long i = 2;
  for (i; num/i >= i; i++) {
    if (num % i == 0) {
      return 0;
    }
  }
  return 1;
}

Существует много улучшений производительности, возможно с простым определением,Тем не менее, это должно привести к тому, что код «не работает с большими числами».

---

¹ Хорошие компиляторы будут видеть ближайшие num/i и num%i и часто их вычислятьвместе примерно столько же времени, сколько один.

Answer 2

Вам нужно найти сопряжения, меньшие 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.