//题意：给你n个数（可能有重复），问你最多可以取出多少个数使得任意两个数之和为质数。
//题解：以为是个C（2，n）复杂度，结果手摸几组，发现从奇偶性考虑，只有两种情况：有1，可以取出所有的1，并可以再取一个偶数（如果这个偶数+1是质数）。没有1，如果取了一个奇质数，那只能再拿一个2（如果有2的话）。
坑：一度把题目记错了，以为输入的是质数，结果比赛的时候一直wa到orz
ac代码：
#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
const int maxn = (1e6 + ) * ;
const int mod = 1e9 + ;
int isp[maxn];
int p[];
void setp() { for (int i = ; i <= maxn; i++)isp[i] = ;
isp[] = ;
for (int i = ; i*i <= maxn; i++)if (isp[i]) {
int x = i;
while (x*i <= maxn) {
isp[x*i] = ;
x++;
}
}
}
int main() {
int n;
cin >> n;
int cnt = , c2 = ;
setp();
//for(int i=1;i<=5;i++)if(isp[i])cout<<i<<' ';
for (int i = ; i <= n; i++) {
cin >> p[i];
if (p[i] == )cnt++;
if (p[i] == )c2 = ;//题目记错了
}
if (cnt >= ) {
//cout << cnt + c2 << endl;
int tmp=;
for (int i = ; i <= n; i++)if (p[i] % == ) {
if (isp[p[i] + ])tmp = p[i];
}
if (tmp==)cout << cnt;
else cout << cnt + ;
cout << endl;
while (cnt--)cout << << ' ';
if (tmp)cout << tmp;
cout << endl; //if (c2)cout << 2;
}
else { sort(p + , p + n + );
for (int i = ; i<n; i++) {
for (int j = i + ; j <= n; j++) {
if (isp[p[i] + p[j]]) { printf("%d\n%d %d", , p[i], p[j]); return ; }
}
}
int okk = ;
for (int i = ; i <= n; i++)if (isp[p[i]]) { okk = p[i]; break; }
if (okk) printf("%d\n%d", , okk);
else cout << << endl, cout << p[];//莫名其妙的一句，忘了当时为啥加的 }
}