数组互质对数统计超时问题及高效公因数判断方法咨询

看来你因为判断两数是否互质的方式效率过低，导致代码在测试用例中超时了。咱们来拆解问题，一步步优化：

原代码的核心问题 #

你原来的三重循环里，最内层要从2遍历到list[j]来检查公因数——如果数组里的数值很大（比如几万甚至几十万），这个循环会执行成千上万次，时间复杂度直接飙升到O(n²*m)（n是数组长度，m是元素最大值），超时是必然的。

高效判断互质的关键：最大公约数（GCD） #

两个数互质的充要条件是它们的最大公约数等于1。而用欧几里得算法计算GCD的时间复杂度是O(log(min(a,b)))，比线性遍历快得多，能大幅降低整体耗时。

第一步：实现快速GCD函数 #

先写一个高效的GCD计算函数：

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

第二步：修改原代码替换低效判断 #

把原来的内层循环替换成GCD判断，直接检查两数是否互质：

double estimate_PI(int list[], int size) { 
    int total_pairs = size * (size - 1) / 2; 
    int coprime_count = total_pairs; 

    for (int i = 0; i < size; i++) { 
        for (int j = i + 1; j < size; j++) { 
            // 若GCD不等于1，说明两数有大于1的公因数，非互质
            if (gcd(list[i], list[j]) != 1) { 
                coprime_count--; 
            } 
        } 
    } 

    double PI = sqrt(6.0 * total_pairs / coprime_count); 
    return PI; 
}

进阶优化（针对超大规模数组） #

如果你的数组规模特别大（比如十万级以上），还可以做这些优化：

• 统计元素频率：先统计每个数出现的次数，避免重复计算相同数对的GCD，减少冗余操作。
• 质因数分解+容斥原理：先对每个数做质因数分解，再用容斥原理计算非互质数对的总数，进一步降低时间复杂度，但实现起来稍复杂，对于大多数CodeCrunch测试用例，上面的GCD方法已经足够通过所有用例了。

为什么这个优化能解决超时？ #

举个例子：如果数组里有一个1000000的数，原来的内层循环要执行近百万次；而用GCD计算，最多只需要20次左右的迭代就能得出结果，效率提升了几个数量级。

内容的提问来源于stack exchange，提问作者Zhe Feng Zhang