亲和数、素数分拆与回文质数的算法实现与优化

1. 亲和数问题解析与实现

1.1 问题背景与数学原理

亲和数（Amicable Numbers）是指两个不同的自然数，其中每个数的真约数之和等于另一个数。这个概念最早由古希腊数学家毕达哥拉斯发现，220和284是最小的一对亲和数。

真约数（Proper Divisor）是指能整除该数但不包括该数本身的自然数。例如：

• 220的真约数：1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110
• 284的真约数：1, 2, 4, 71, 142

1.2 算法设计与优化

基础实现方案是遍历1到n-1的所有数，检查是否为n的约数。但这种方法效率较低，对于大数（如600000）需要优化：

cpp复制int sumProperDivisors(int n) {
    if(n == 1) return 0;
    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;
}

优化点：

1. 只需遍历到√n，减少循环次数
2. 当i是约数时，n/i也是约数
3. 处理平方数特殊情况

1.3 完整实现与测试

cpp复制#include <iostream>
using namespace std;

int sumProperDivisors(int n) {
    if(n == 1) return 0;
    int sum = 1;
    for(int i = 2; i*i <= n; i++) {
        if(n % i == 0) {
            sum += i;
            if(i != n/i) sum += n/i;
        }
    }
    return sum;
}

int main() {
    int M;
    cin >> M;
    while(M--) {