素数分拆与亲和数问题的算法实现与优化

1. 分拆素数和问题解析

1.1 问题背景与数学原理

素数分拆问题源于数论中的一个经典命题：任何一个大于2的偶数都可以表示为两个素数之和（哥德巴赫猜想）。虽然这个猜想尚未被完全证明，但在有限范围内（如题目中的10000以内）我们可以通过编程验证。

素数判断的核心原理是：一个大于1的自然数，除了1和它本身外没有其他约数。优化判断时只需检查到√n即可，因为如果n能被大于√n的数整除，那么对应的商必定小于√n，已经被检查过。

1.2 算法实现详解

c复制#include <stdio.h>

// 时间复杂度O(√n)的素数判断
int is_prime(int num) {
    if (num < 2) return 0;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return 0;
    }
    return 1;
}

int main() {
    int T;
    scanf("%d", &T);
    
    while (T--) {
        int n, count = 0;
        scanf("%d", &n);
        
        // 关键优化：只需遍历到n/2避免重复计数
        for (int p = 2; p < n/2; p++) {
            if (is_prime(p) && is_prime(n - p)) {
                count++;
            }
        }
        
        printf("%d\n", count);
    }
    return 0;
}

注意：p < n/2的条件确保了(p, q)和(q, p)不会被重复计数，同时自动排除了p=q的情况

1.3 性能优化技巧

1. 素数预计算：对于多次查询，可以预先用筛法（如埃拉托斯特尼筛法）计算出范围内的所有素数，存储为哈希表或数组

2. 边界处理：当n=4时直接返回0，因为2是唯一的偶素数，2+2不符合"不同素数"要求

3. 循环步长优化：除了2