登录以参加训练计划

质数的定义

质数（Prime Number）又称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

判断质数

bool isprime(int x) {
    if(x <= 1) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

埃氏筛法（Sieve of Eratosthenes）

埃拉托斯特尼筛法是一种高效找出一定范围内所有质数的算法。

基本思想

1. 从 2 开始，将每个质数的倍数标记为非质数
2. 对于每个未标记的数，将其标记为质数
3. 重复以上过程，直到遍历到 √max

C++实现

const int MAXN = 1e7 + 5;
bool isprime[MAXN];

void init() {
    memset(isprime, true, sizeof(isprime));
    isprime[1] = false;
    for (int i = 2; i * i <= MAXN; i++) {
        if (isprime[i]) {
            for (int j = i; j * i <= MAXN; j++) {
                isprime[j * i] = false;
            }
        }
    }
}

哥德巴赫猜想

任意大于9的奇数都可以表示为3个质数之和。

解题思路

1. 使用埃氏筛法预处理所有质数
2. 枚举两个质数，寻找第三个质数使得三数之和等于目标值
3. 按字典序输出最小的解