c - 检查数组中的数字是否有公因数的省时方法？

Question

这个作业的目的是找出数组中每两个数字可以组成的对的数量。条件是这两个数不能有公因数。

我尝试使用循环比较数组中的数字，并使用从 2 开始的因子循环。此代码可以工作，但在 codecrunch 上超过了十分之 2 的时间限制。

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;
}

对于这种方法，代码运行需要很长时间，这表明我错了。

Answer 1

与其尝试每个值[2...list[j])，不如寻找Greatest common divisor

示例int gcd(int a, int b) Arjun Sreedharan或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 的因子。