экономящий время способ проверить, имеют ли числа в массиве общий фактор? - PullRequest
Новая
       49

экономящий время способ проверить, имеют ли числа в массиве общий фактор?

0 голосов
/ 30 марта 2019

Цель этого задания - найти количество пар, которые можно сформировать из каждых двух чисел в массиве.Условие состоит в том, что эти два числа не могут иметь общих множителей.

Я пытался использовать цикл сравнения числа по номеру в массиве с циклом фактора, начинающимся с 2. Этот код работает, но он превышает ограничение по времени для2 из 10 случаев использования codecrunch. 

double estimate_PI(int list[], int size) {
  int i, pair;
  pair = size * (size - 1) / 2; //total number of pairs can be formed

  int count = pair;
  int j, l;
  for (i = 0; i < size; i++) {        //check the first number in the array
    for (j = i + 1; j < size; j++) { //check compare the first number of the rest 
      // of the numbers in the array 
      for (l = 2; l < list[j]; l++) {           //check for common factors
        if (list[i] % l == 0 && list[j] % l == 0) { //if these two values have common factor
          count--;                 //the possible number of pair reduce by 1
          break;
        }
      }
    }
  }
  //  printf("%d\n count",count);
  double PI = sqrt(6.0000 * pair / count);
  return PI;
}

Этот метод требует слишком много времени для запуска codecrunch и помечает меня неправильно.

1 Ответ

0 голосов
/ 30 марта 2019

Вместо того, чтобы пробовать каждое значение [2...list[j]), возможно, ищите Величайший общий делитель

Пример int gcd(int a, int b) Арджун Шридхаран или chux 

#if 0
  for (l = 2; l < list[j]; l++) {           //check for common factors
    ...
  }
#else
  if (gcd(list[i], list[j]) <= 1) count--;
#endif

Упрощение возможно, так как необходимо найти только первый фактор> 1.

...