#include<bits/stdc++.h>
using namespace std;
long n,i,s,j,x,k;
bool f[2000005];
int main()
{
	cin>>n;
	f[1]=1;
	for(j=2;j<=sqrt(1000006);j++)
		if(!f[j])
			for(k=j;k<=1000006/j;k++)
				f[j*k]=1;//预处理素数
	for(i=1;i<=n;i++)//暴力枚举
	{
		s=0;
		cin>>x;
		for(j=2;j<x;j++)
			if(!f[j]&&!f[x-j])
			{
				cout<<x<<'='<<j<<'+'<<x-j<<endl;
				s=1;
				break;
			}
		if(!s)cout<<"NO WAY!"<<endl;
	}
	return 0;
}

简单水题，此题就是将P36的一组数据改成多组数据，求积改成求和而已。

如果不明白求素数，请移步http://112.16.216.176:29860/d/zjzx/p/36/solution。如果链接挂了就手动来到P36的题解区。

Q：埃氏筛有什么作用？

A：如果要在同一个给定范围内查询很多数是不是素数，这种方法能优化时间复杂度。

埃氏筛思路：

我们先假设false代表这个数是素数，且刚开始埃氏筛范围内的所有数全部都是素数。

*不难想到，一个数的倍数一定不是素数，但是，这样枚举的话会浪费大量时间，复杂度几乎等价于求素数。那么就需要优化：

*如果一个数已经被筛过，那么他的倍数肯定也被筛过。

因此，在埃氏筛的时候，内循环只有在这个数没被筛过的时候才执行。

代码(prime函数就是埃氏筛的模板）：

#include <bits/stdc++.h>
using namespace std；
int n,m;
bool p[10010];
inline bool prime ( int n ) }//核心代码
	p [ 0 ] = p [ 1 ] = true ;//0和1都不是素数
	for ( int i = 2 ; i * i <= n ; ++i ) {//同等于2到sqrt(n)
		if ( ! p [ i ] ) {//如果还没被筛到或者它是素数
			for ( int j = 2 ; i * j <= n ; ++j ) {//枚举2到n之间除了i以外的i的倍数
				p [ i * j ] = true ;//将它变成非素数
			}
		}
	}
}
int main () {
	cin >> m ;
	prime ( 1e6 ) ;//1e6=10^6
	while ( m-- ) {
		cin >> n ;
		bool f = true ;
		for ( int i = 2 ; i <= n ; ++ i ) {
			if ( ! p [ i ] && ! p [ n - i ] ) {//模拟
				cout << n << '=' << i << '+' << n - i << '\n' ;
				f = false ;
				break;
			}
		}
		if ( f ) cout << "NOWAY!\n" ;
	}
	return o;
}

#include <iostream> #include <cstdio> #include <cmath>

using namespace std;

int m, n[55], maxn; int p[1000005]; int a[100005], cnt;

int main() { scanf("%d", &m); for(register int i = 1; i <= m; ++i) { scanf("%d", n + i); if(n[i] > maxn) maxn = n[i]; } for(register int i = 2; i <= maxn; ++i) { if(!p[i]) a[++cnt] = i; for(register int j = 1; i * a[j] <= maxn; ++j) { p[i * a[j]] = 1; if(!(i % a[j])) break; } } int op; for(register int i = 1; i <= m; ++i) { op = 0; for(register int j = 1; a[j] <= n[i] - a[j]; ++j) { if(!p[n[i] - a[j]]) { printf("%d=%d+%d\n", n[i], a[j], n[i] - a[j]); op = 1; break; } } if(!op) printf("NO WAY!\n"); } return 0; }