C++数学算法实践：完数、阶乘配对与因子分解

markdown复制## 1. 实验目标与背景解析

这次C++实验涵盖了四个经典数学问题的编程实现：完数判定、阶乘配对、整数因子分解以及半素数识别。这些题目看似基础，实则包含了循环控制、算法优化、数学建模等核心编程思想。我在大学任教时，常把这些题目作为从"语法学习"过渡到"算法思维"的桥梁。

完数（Perfect Number）指等于其真因子之和的数，比如6=1+2+3。阶乘配对考察大数阶乘的质因数分解特性。整数因子分解是密码学的基础操作，而半素数（两个质数的乘积）在RSA加密中有重要应用。通过这组实验，我们能系统训练：

1. 循环结构的嵌套与优化
2. 数学定理的编程转化
3. 算法时间复杂度的控制
4. 边界条件的处理技巧

## 2. 核心算法实现详解

### 2.1 完数判定算法

完数判定的关键在于高效计算真因子和。传统方法是遍历1到n/2找因子，但存在优化空间：

```cpp
bool isPerfect(int n) {
    if (n <= 1) return false;
    int sum = 1; // 1是所有大于1的数的真因子
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) sum += n / i;
        }
    }
    return sum == n;
}

注意：循环终止条件设为i*i<=n可将时间复杂度从O(n)降到O(√n)。当找到因子i时，其对应因子n/i也需要加入，但要避免重复添加平方数的情况。

2.2 12!的质因数配对

计算12!的质因数分解，并找出所有因子对(a,b)使得a*b=12!。这里需要：

1. 先对12!进行质因数分解
2. 根据质因数展开生成所有因子
3. 配对时避免重复计数

cpp复制vector<pair<int,int>> factorPairs() {
    const int N = 479001600; // 12!
    vector<int> factors;
    for (int i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            factors.push_back(i);
            if (i != N / i) factors.push_back(N / i);
        }
    }
    
    vector<pair<int,int>> pairs;
    for (int i = 0; i < factors.size(); ++i) {
        for (int j = i; j < factors.size(); ++j) {
            if (factors[i] * factors[j] == N) {
                pairs.emplace_back(factors[i], factors[j]);
            }
        }
    }
    return pairs;
}

2.3 整数因子分解

实现整数分解为质因数的乘积形式，如12=2²×3¹。采用试除法：

cpp复制map<int,int> primeFactorization(int n) {
    map<int,int> factors;
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    if (n > 1) factors[n]++;
    return factors;
}

实测技巧：当n是合数时，至少有一个质因子≤√n。每次找到因子后彻底除尽该因子，能显著减少后续计算量。

2.4 半素数识别

半素数指恰好两个质数的乘积（可以相同）。快速判定算法：

cpp复制bool isSemiprime(int n) {
    int cnt = 0;
    for (int i = 2; i * i <= n && cnt <= 2; ++i) {
        while (n % i == 0) {
            n /= i;
            cnt++;
        }
    }
    if (n > 1) cnt++;
    return cnt == 2;
}

3. 性能优化与边界处理

3.1 预处理质数表

对于频繁的质数判断，可预先用埃拉托斯特尼筛法生成质数表：

cpp复制vector<bool> sieve(int max_num) {
    vector<bool> is_prime(max_num + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= max_num; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max_num; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;
}

3.2 大数处理的注意事项

1. 阶乘计算极易溢出，12!已经达到4.7亿，应使用long long类型
2. 因子配对时注意乘积是否超过INT_MAX
3. 循环终止条件统一使用i*i<=n避免整数溢出

3.3 常见错误排查表

4. 扩展应用与进阶思考

这些基础算法在实际工程中有广泛延伸：

1. 完数搜索与梅森素数的关系
2. 因子分解在RSA破解中的应用
3. 半素数在公钥密码体系中的作用
4. Pollard's Rho等高级分解算法

我在实现RSA加密demo时，就曾因半素数生成算法效率低下导致性能瓶颈。后来改用Miller-Rabin素性测试配合预生成质数表，速度提升了20倍。这提醒我们：基础算法的优化往往能带来意想不到的收益。

建议尝试用这些算法解决：

• 找出10000以内的所有完数
• 比较不同因子分解算法的效率
• 生成指定位数的半素数

code复制