如何用C++高效计算1到n范围内约数个数为偶数的整数个数？

在C++中高效计算1到n范围内约数个数为偶数的整数个数，核心结论为：结果等于 n 减去 1到n中完全平方数的个数，即 n - (long long)sqrt(n)。

判断依据

根据数论性质，正整数的约数总是成对出现的（若 d 是 n 的约数，则 n/d 也是）。只有当 d = n/d，即 n = d² 时，这对约数重合为一个，导致约数总数为奇数。因此：

• 完全平方数的约数个数为奇数；
• 非完全平方数的约数个数为偶数。 1到n中完全平方数的个数恰好为 floor(sqrt(n))。

C++实现步骤

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

int main() {
    long long n;
    cin >> n;
    long long sq = sqrt(n);
    // 修正浮点误差
    while ((sq + 1) * (sq + 1) <= n) sq++;
    while (sq * sq > n) sq--;
    cout << n - sq << endl;
    return 0;
}

适用条件

• 适用于 n 较大的场景，时间复杂度 O(1)，远优于逐个枚举约数的 O(n√n) 方法。
• 需使用 long long 防止大数溢出。

常见误区

1. 直接遍历统计：逐个计算每个数的约数个数再判断奇偶，效率极低，不适用于大范围。
2. 浮点精度问题：sqrt() 返回 double，强转为整数时可能因精度丢失导致结果差1，必须用相邻整数校验修正。
3. 混淆奇偶条件：误认为质数或其他特殊数的约数个数为偶数，实际上所有非完全平方数约数个数均为偶数。