优化100000-200000区间最多约数数求解代码的运行时长

我是一名10年级学生，老师布置的练习题中有一道要求：找出100000到200000之间约数最多的数（即能被最多整数整除的数）。我编写了一段C++代码，但运行时长达到32秒，甚至无法验证答案是否正确，现询问如何优化代码以缩短运行时间。

我编写的代码如下：

void f3() {
    int mostcount = 0, most, divisors = 0;
    for (int i = 100000; i <= 200000; i++) {
        for (int j = 1; j<=i/2; j++) {
            if (i % j == 0) {
                divisors++;
            }
        }
        if (divisors > mostcount) {
            mostcount = divisors;
            most = i;
        }
        divisors = 0;
    }
    cout << most << endl;
    return;
}

当前输出结果为：166320

1. 缩小约数计数的循环范围 #

原来的代码循环到i/2，但约数是成对出现的：如果j是i的约数，那么i/j也一定是i的约数。所以只需要循环到sqrt(i)就能统计所有约数，这能把单个数的循环次数从几万次降到几百次，直接大幅提升速度。

2. 处理平方数的特殊情况 #

当j*j == i时，j和i/j是同一个数，这时候只能算1个约数，避免重复计数。

3. 优化变量初始化 #

把divisors的初始化放到外层循环的开头，避免每次循环结束后清零再重新赋值，减少不必要的操作。

4. 进阶：用筛法预处理约数个数 #

如果范围更大，还可以用类似埃氏筛的方法，遍历每个数的倍数，给每个倍数的约数计数加1。这种方法时间复杂度更低，适合大范围的数值统计。

优化后的代码（直接计数版） #

#include <iostream>
#include <cmath>
using namespace std;

void f3() {
    int mostcount = 0, most;
    for (int i = 100000; i <= 200000; i++) {
        int divisors = 0;
        int sqrt_i = sqrt(i);
        for (int j = 1; j <= sqrt_i; j++) {
            if (i % j == 0) {
                // 成对的约数
                if (j * j == i) {
                    divisors++;
                } else {
                    divisors += 2;
                }
            }
        }
        if (divisors > mostcount) {
            mostcount = divisors;
            most = i;
        }
    }
    cout << "约数最多的数是：" << most << "，共有" << mostcount << "个约数" << endl;
}

int main() {
    f3();
    return 0;
}

进阶优化：筛法版 #

#include <iostream>
#include <vector>
using namespace std;

void f3() {
    const int MAX = 200000;
    vector<int> divisor_count(MAX + 1, 0);
    
    // 筛法统计每个数的约数个数
    for (int j = 1; j <= MAX; j++) {
        for (int i = j; i <= MAX; i += j) {
            divisor_count[i]++;
        }
    }
    
    int mostcount = 0, most;
    for (int i = 100000; i <= MAX; i++) {
        if (divisor_count[i] > mostcount) {
            mostcount = divisor_count[i];
            most = i;
        }
    }
    cout << "约数最多的数是：" << most << "，共有" << mostcount << "个约数" << endl;
}

int main() {
    f3();
    return 0;
}

这两种优化后的代码运行时间都会远低于32秒，甚至能在毫秒级完成计算。你可以验证一下，166320确实是这个区间里约数较多的数，用优化后的代码能准确统计出它的约数个数，也能确认是否存在其他约数更多的数。

内容的提问来源于stack exchange，提问作者Krisztián