这个作业的目的是找出数组中每两个数字可以组成的对的数量。条件是这两个数不能有公因数。
我尝试使用循环比较数组中的数字,并使用从 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;
}
对于这种方法,代码运行需要很长时间,这表明我错了。
最佳答案
与其尝试每个值[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 的因子。
关于c - 检查数组中的数字是否有公因数的省时方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55431921/