<= 求赞qwq，码字不易，你的支持是我写作的动力

宣传一下算法提高课题解合集

1292.哥德巴赫猜想

线性筛是一种可以在 $O(n)$ 的时间复杂度内快速筛出 $1 \sim n$ 的素数的算法

线性筛保持复杂度线性的关键点在于：每个点只会被这个数的最小质因子筛掉

我们记录 $v_i$ 表示数字 $i$ 是否是质数，$prime_i$ 来记录第 $i$ 小的质数，$cnt$ 来记录 $prime$ 数组的大小

const int N = 1000009;
int cnt, prime[N];
bool v[N];

接着，我们通过代码来详解线性筛：

void get_prime(int n)
//线性筛函数，n 表示一共要筛几个数
{
    v[1] = true;
    //1 显然不是质数

    for(int i = 2;i <= n;++ i)
    //枚举所有小于等于 n 的数
    //因为一个数的最小质因子显然小于等于这个数，所以
    //我们从小到大枚举 i

    {
        if (!v[i]) prime[cnt ++] = i;
        //如果数 i 已经没有被更新过了，那么这个数就是
        //质数，所以 prime 数组增加这个质数

        for(int j = 0;prime[j] <= n / i;++ j)
        //从小到大枚举所有已知质数

        {
            v[prime[j] * i] = true;
            //显然，prime[j] * i 是一个合数

            if (i % prime[j] == 0) break;
            //如果 i % primes[j] == 0，primes[j] 一定是
            //i 的最小质因子 (因为是从小到大遍枚举 j)
            //primes[j] 一定是 primes[j] * i 的最小质因子

            //如果 i % primes[j] != 0，primes[j] 一定是
            //小于 i 的所有质因子，primes[j] 也一定是
            //primes[j] * i的最小质因子
        }
    }
}

在线性筛过后，我们再返回题目

本体是要求我们判断一个数是否能够划分成两个质数的和

直接暴力枚举所有 $prime$ 数组内的质数即可

例如：当我们枚举到质数 $i$ 时，另一个数为原数减去 $i$

判断原数减去 $i$ 是否为质数用 $v$ 数组即可

c++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1000009;

int prime[N], cnt, n;
bool v[N];

void get_prime(int n)
{
    v[1] = true;
    for(int i = 2;i <= n;++ i)
    {
        if (!v[i]) prime[cnt ++] = i;
        for(int j = 0;prime[j] <= n / i;++ j)
        {
            v[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

int main()
{
    get_prime(N - 5);

    while(cin >> n && n)
    {
        int i = 1;
        while(i)
        {
            if(!v[n - prime[i]])
            {
                cout << n << " = " << prime[i] << " + " << n - prime[i] << endl;
                break;
            }
            i ++;
        }
    }
}

参考资料：https://www.acwing.com/solution/content/22512/