题意

给定多个偶数,找两个质数使得其和为该偶数,且这两个质数之差最小

限制,偶数在$[4,1000][4,1000]$之间

方法

预处理

我们先计算出质数表,随后枚举质数对,计算它们的和,更新结果

以题目的20为例,考虑小于20的质数有$2,3,5,7,11,13,17,192,3,5,7,11,13,17,19$,我们只考虑和为偶数的情况

以下展示了v2pair20以内的变化情况

那么对于20来说答案就是7和13了

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
vector<pair<int,int> > v2pair(1001,make_pair(0,0));
int main(){
    vector<bool> p(1001,true); // 质数表
    rep(i,2,1001){
        if(!p[i])continue;
        rep(j,i,1001){
            if(i*j>1000)break;
            p[i*j] = false;
        }
    }
    rep(i,2,1001){ // 枚举小质数
        if(!p[i])continue;
        rep(j,i,1001){ // 枚举大质数
            if(!p[j])continue;
            if(i+j > 1000)break; // 控制和的范围
            // {0,0} 或 差值更大
            if(v2pair[i+j].first + v2pair[i+j].second != i+j || v2pair[i+j].second - v2pair[i+j].first > j-i){
                v2pair[i+j] = {i,j}; // 更新最小差的两个质数
            }
        }
    }
    int n;
    while(~scanf("%d",&n)){
        printf("%d\n%d\n",v2pair[n].first,v2pair[n].second);
    }
    return 0;
}

复杂度分析

设有m个查询

时间复杂度: 初始化质数表$O(n)O(n)$,枚举所有质数对的时间复杂度为$O(n^2)O(n^2)$,对于每个查询$O(1)O(1)$,所以总时间复杂度为$O(n^2+m)O(n^2+m)$

空间复杂度: 两部分,一个是质数表储存,一个是预处理的结果储存,两部分都是$O(n)O(n)$,所以总时间复杂度为$O(n)O(n)$

每次搜索

我们同样预先计算出质数表,但是我们不计算结果,每次查询时再去搜"质数"和"当前偶数减去一个质数"

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
int main(){
    vector<bool> p(1001,true); // 质数表
    rep(i,2,1001){
        if(!p[i])continue;
        rep(j,i,1001){
            if(i*j>1000)break;
            p[i*j] = false;
        }
    }
    int n;
    while(~scanf("%d",&n)){
        pair<int,int> ans={0,n}; // 初始化和
        rep(i,2,1001){
            if(!p[i])continue; // i 是质数
            int j = n-i; // 当前偶数减去一个质数
            if(j < i)break; // j>=i
            if(!p[j])continue; // j 是质数
            ans={i,j};
        }
        printf("%d\n%d\n",ans.first,ans.second);
    }
    return 0;
}

复杂度分析

时间复杂度: 初始化质数表$O(n)O(n)$, 对于每个查询最坏代价是$O(n)O(n)$,所以总时间复杂度为$O(mn)O(mn)$

空间复杂度: 我们额外空间主要是质数表,其余空间都是常数大小,所以总空间复杂度为$O(n)O(n)$