题解

先埃式筛一遍，再遍历判断

#include <iostream>
#include <cstdio>
using namespace std;
bool vis[1000005];
int prime[100005], ct;
void _init(int n){//埃式筛O(nloglogn)
    vis[0] = vis[1] = 1;
	for(int i = 2; i * i <= n; i++){
		if(!vis[i]){
			for(int j = i * 2; j <= n; j += i){
				vis[j] = 1;
			}
		}
	}for(int i = 2; i <= n; i++){
		if(!vis[i]) prime[++ct] = i;
	}
}bool isprime(int x){
	if(x < 2) return 0;
	if(x == 2) return 1;
	if(x % 2 == 0) return 0;
	for(int i = 3; i * i <= x; i += 2){
		if(x % i == 0) return 0;
	}return 1;
}
int main(){
	int n;
	cin >> n;
	_init(n);
	for(int i = 4; i <= n; i += 2){
		for(int j = 1; j <= ct && prime[j] < i; j++){
			int x = prime[j];
			int y = i - x;
			if(!vis[y]){//判断质数就降到了O(1)
				printf("%d=%d+%d\n", i, x, y);
				break;
			}
		}
	}
	

	return 0;
}

时间复杂度：$O(n^2)$