A tuple of positive integers {x_1, x_2, ..., x_{k}} is called simple if for all pairs of positive integers (i,  j) (1  ≤ i  <  j ≤ k), x_{i}  +  x_{j} is a prime.

You are given an array a with n positive integers a_1,  a_2,  ...,  a_{n} (not necessary distinct). You want to find a simple subset of the array a with the maximum size.

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Let's define a subset of the array a as a tuple that can be obtained from a by removing some (possibly all) elements of it.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of integers in the array a.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^6) — the elements of the array a.


-----Output-----

On the first line print integer m — the maximum possible size of simple subset of a.

On the second line print m integers b_{l} — the elements of the simple subset of the array a with the maximum size.

If there is more than one solution you can print any of them. You can print the elements of the subset in any order.


-----Examples-----
Input
2
2 3

Output
2
3 2

Input
2
2 2

Output
1
2

Input
3
2 1 1

Output
3
1 1 2

Input
2
83 14

Output
2
14 83

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Number theory

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
def main():
	input()
	(l0, l1, ones) = ([], [], 0)
	for a in map(int, input().split()):
		if a == 1:
			ones += 1
		else:
			(l1 if a & 1 else l0).append(a)
	seive = [False, True] * (((max(l0) if l0 else 0) + (max(l1) if l1 else 0)) // 2 + 1)
	a = len(seive)
	for i in range(3, int(a ** 0.5) + 1, 2):
		if seive[i]:
			for j in range(i * i, a, i):
				seive[j] = False
	if ones:
		res = ['1'] * ones
		for a in l0:
			if a > 1 and seive[a + 1]:
				res.append(str(a))
				break
		if len(res) > 1:
			print(len(res))
			print(' '.join(res))
			return
	for a in l1:
		for b in l0:
			if seive[a + b]:
				print(2)
				print(a, b)
				return
	print(1)
	print(1 if ones else (l0 if l0 else l1)[0])

def __starting_point():
	main()
__starting_point()


import math
n = int(input())
a = [int(x) for x in input().split()]
p1 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511]
primes = dict(map(lambda x: (x, True), p1))

def isPrime(v):
	if v in primes:
		return primes[v]
	sqrti = math.sqrt(v)
	for i in range(len(p1)):
		if v % p1[i] == 0:
			primes[v] = False
			return False
		if p1[i] > sqrti:
			break
	primes[v] = True
	return True
done = False
cnt1 = sum(filter(lambda x: x == 1, a))
if cnt1 > 1:
	for i in range(n):
		if a[i] != 1 and isPrime(a[i] + 1):
			done = True
			print(cnt1 + 1)
			print(a[i], end=' ')
			print(str.join(' ', ['1'] * cnt1))
			break
	if not done:
		done = True
		print(cnt1)
		print(str.join(' ', ['1'] * cnt1))
else:
	for i in range(n):
		for j in range(n):
			if i != j and isPrime(a[i] + a[j]):
				done = True
				print(2)
				print(f'{a[i]} {a[j]}')
				break
		if done:
			break
	if not done:
		print(1)
		print(a[0])


from time import time
n = int(input())
a = list(map(int, input().split()))
start = time()
cache = {}

def is_prime(n):
	if n not in cache:
		cache[n] = _is_prime(n)
	return cache[n]

def _is_prime(n):
	if n == 2 or n == 3:
		return True
	if n < 2 or n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	r = int(n ** 0.5)
	f = 5
	while f <= r:
		if n % f == 0:
			return False
		if n % (f + 2) == 0:
			return False
		f += 6
	return True
s = {}
i = 0
while i < len(a):
	if a[i] > 1 and a[i] in s:
		a.pop(i)
	else:
		s[a[i]] = True
		i += 1
p = [0] * len(a)
for i in range(0, len(a)):
	for j in range(i + 1, len(a)):
		if not is_prime(a[i] + a[j]):
			p[i] += 1
			p[j] += 1
while True:
	mx = max(p)
	if mx == 0:
		break
	mi = p.index(mx)
	for i in range(0, len(a)):
		if i == mi or not is_prime(a[mi] + a[i]):
			p[i] -= 1
	a.pop(mi)
	p.pop(mi)
print(len(a))
print(' '.join(map(str, a)))


def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
n = int(input())
arr = list(map(int, input().split()))
count = {}
for i in arr:
	try:
		count[i] += 1
	except KeyError:
		count[i] = 1
numbers = list(count.keys())
numbers.sort()
(a, b) = (-1, -1)
flag = False
for i in range(len(numbers) - 1):
	for j in range(i + 1, len(numbers)):
		if isPrime(numbers[i] + numbers[j]):
			a = numbers[i]
			b = numbers[j]
			flag = True
			break
	if flag:
		break
if a == b and a == -1:
	if numbers[0] == 1 and count[1] > 1:
		print(count[1])
		for i in range(count[1]):
			print(1, end=' ')
		print()
	else:
		print(1)
		print(numbers[0])
elif a == 1:
	print(count[1] + 1)
	for i in range(count[1]):
		print(1, end=' ')
	print(b)
elif numbers[0] == 1 and count[1] > 2:
	print(count[1])
	for i in range(count[1]):
		print(1, end=' ')
	print()
else:
	print(2)
	print(a, b)


def main():
	n = int(input())
	l = list(map(int, input().split()))
	seive = [False, True] * max(l)
	a = len(seive)
	for i in range(3, int(a ** 0.5) + 1, 2):
		if seive[i]:
			for j in range(i * i, a, i):
				seive[j] = False
	i = l.count(1)
	if i:
		res = [1] * i
		for a in l:
			if a > 1 and seive[a + 1]:
				res.append(a)
				break
		if len(res) > 1:
			print(len(res))
			print(*res)
			return
	(l0, l1) = ([], [])
	for a in l:
		if a != 1:
			if a & 1:
				for b in l0:
					if seive[a + b]:
						print(2)
						print(a, b)
						return
				l1.append(a)
			else:
				for b in l1:
					if seive[a + b]:
						print(2)
						print(a, b)
						return
				l0.append(a)
	print(1)
	print(l[0])
main()


import sys

def get_primes(n: int):
	from itertools import chain
	from array import array
	primes = {2, 3}
	is_prime = array('b', (0, 0, 1, 1, 0, 1, 0)) + array('b', (1, 0, 0, 0, 1, 0)) * ((n - 1) // 6)
	for i in chain.from_iterable((list(range(5, n + 1, 6)), list(range(7, n + 1, 6)))):
		if is_prime[i]:
			primes.add(i)
			for j in range(i * 3, n + 1, i * 2):
				is_prime[j] = 0
	return (is_prime, primes)
n = int(input())
a = list(map(int, input().split()))
(is_prime, primes) = get_primes(2 * 10 ** 6)
one_count = a.count(1)
if one_count > 1:
	for i in range(n):
		if a[i] != 1 and is_prime[a[i] + 1]:
			print(one_count + 1)
			print(*[1] * one_count + [a[i]])
			return
	else:
		print(one_count)
		print(*[1] * one_count)
else:
	for i in range(n):
		for j in range(n):
			if i != j and is_prime[a[i] + a[j]]:
				print(2)
				print(a[i], a[j])
				return
	else:
		print(1)
		print(a[0])


import sys
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue
from math import *
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mx = 2 * 10 ** 6 + 10
prime = [1 for i in range(2 * 10 ** 6 + 10)]
prime[0] = 0
prime[1] = 0
p = 2
while p * p < mx:
	if prime[p] == 1:
		for i in range(p * p, mx, p):
			prime[i] = 0
	p += 1
n = ii()
a = il()
d = {}
for i in a:
	d[i] = d.get(i, 0) + 1
if d.get(1) and d[1] >= 2:
	for i in range(n):
		if a[i] > 1 and prime[a[i] + 1] == 1:
			print(d[1] + 1)
			for j in range(d[1]):
				print(1, end=' ')
			print(a[i])
			exit(0)
	print(d[1])
	t = 0
	for i in range(d[1]):
		print(1, end=' ')
	exit(0)
for i in range(n):
	for j in range(i + 1, n):
		if prime[a[i] + a[j]] == 1:
			print(2)
			print(a[i], a[j])
			exit(0)
print(1)
print(a[0])


n = int(input())
L = list(map(int, input().split()))
P = [-1 for _ in range(2000001)]

def premier(n):
	if P[n] >= 0:
		return P[n]
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			P[n] = False
			return False
	P[n] = True
	return True
e = L.count(1)
if n == 1:
	print(1)
	print(L[0])
elif e > 1:
	L.sort()
	i = 1
	while i < n and L[i] == 1:
		i += 1
	u = i
	ok = 0
	while i < n:
		if premier(L[i] + 1):
			print(u + 1)
			for j in range(u):
				print(1, end=' ')
			print(L[i])
			ok = 1
			break
		i += 1
	if ok == 0:
		print(u)
		for i in range(u):
			print(1, end=' ')
else:
	ok = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			t = premier(L[i] + L[j])
			if t:
				print(2)
				print(str(L[i]) + ' ' + str(L[j]))
				ok = 1
				break
		if ok:
			break
	if ok == 0:
		print(1)
		print(L[0])


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def lcm(a, b):
	return a * b // gcd(a, b)
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

def N():
	return int(inp())

def solve():

	def primesbelow(N):
		correction = N % 6 > 1
		N = {0: N, 1: N - 1, 2: N + 4, 3: N + 3, 4: N + 2, 5: N + 1}[N % 6]
		sieve = [True] * (N // 3)
		sieve[0] = False
		for i in range(int(N ** 0.5) // 3 + 1):
			if sieve[i]:
				k = 3 * i + 1 | 1
				sieve[k * k // 3::2 * k] = [False] * ((N // 6 - k * k // 6 - 1) // k + 1)
				sieve[(k * k + 4 * k - 2 * k * (i % 2)) // 3::2 * k] = [False] * ((N // 6 - (k * k + 4 * k - 2 * k * (i % 2)) // 6 - 1) // k + 1)
		return [2, 3] + [3 * i + 1 | 1 for i in range(1, N // 3 - correction) if sieve[i]]
	primes = set(primesbelow(2 * 10 ** 6))
	n = N()
	ar = lis()
	c1 = 0
	pm1 = []
	already = set()
	pr = []
	found = []
	for i in range(n):
		if ar[i] == 1:
			c1 += 1
		if ar[i] + 1 in primes and ar[i] > 1:
			pm1.append(ar[i])
		if ar[i] in primes:
			pr.append(ar[i])
		for j in already:
			if ar[i] + j in primes:
				found.append((j, ar[i]))
		already.add(ar[i])
	if c1 >= 3:
		if pm1:
			print(c1 + 1)
			print('1 ' * c1 + str(pm1[0]))
			return
		else:
			print(c1)
			print('1 ' * c1)
			return
	if c1 == 2:
		if pm1:
			print(c1 + 1)
			print('1 ' * c1 + str(pm1[0]))
			return
	if found:
		print(2)
		print(found[0][0], found[0][1])
		return
	print(1)
	print(ar[0])
solve()


def primes_upto(limit):
	is_prime = [False] * 2 + [True] * (limit - 1)
	for n in range(int(limit ** 0.5 + 1.5)):
		if is_prime[n]:
			for i in range(n * n, limit + 1, n):
				is_prime[i] = False
	return [i for (i, prime) in enumerate(is_prime) if prime]
check = set(primes_upto(2 * 10 ** 6 + 500))
n = int(input())
arr = list(map(int, input().split()))
one_present = False
cnt_ones = 0
for i in arr:
	if i == 1:
		one_present = True
		cnt_ones += 1
(num1, num2, prime) = (0, 0, 0)
for i in range(n):
	for j in range(n):
		if one_present:
			if cnt_ones > 1:
				if arr[i] + arr[j] in check and arr[i] + 1 in check and (arr[j] + 1 in check) and (arr[i] != 1) and (arr[j] != 1):
					num1 = arr[i]
					num2 = arr[j]
				if arr[i] + 1 in check and arr[i] != 1:
					num1 = arr[i]
				if arr[i] in check:
					prime = arr[i]
			else:
				if arr[i] + arr[j] in check and arr[i] != 1 and (arr[j] != 1):
					num1 = arr[i]
					num2 = arr[j]
				if arr[i] + 1 in check and arr[i] != 1:
					num1 = arr[i]
				if arr[i] in check:
					prime = arr[i]
		else:
			if arr[i] + arr[j] in check:
				num1 = arr[i]
				num2 = arr[j]
			if arr[i] in check:
				prime = arr[i]
if one_present:
	if cnt_ones > 1:
		if num2 == 0:
			if num1 == 0:
				print(cnt_ones)
				for i in range(cnt_ones):
					print(1, end=' ')
			else:
				print(cnt_ones + 1)
				for i in range(cnt_ones):
					print(1, end=' ')
				print(num1, end=' ')
		else:
			print(cnt_ones + 2)
			for i in range(cnt_ones):
				print(i, end=' ')
			print(num1, end=' ')
			print(num2, end=' ')
	elif num2 == 0:
		if num1 == 0:
			print(1)
			print(1)
		else:
			print(2)
			print('1 ' + str(num1))
	else:
		print(2)
		print(str(num1) + ' ' + str(num2))
elif num1 == 0:
	if prime == 0:
		print(1)
		print(arr[0])
	else:
		print(1)
		print(prime)
else:
	print(2)
	print(str(num1) + ' ' + str(num2))


import math
N = 2000001
sq = math.floor(N ** 0.5)
isprime = [True] * N
for p in range(2, N):
	if isprime[p]:
		for i in range(p ** 2, N, p):
			isprime[i] = False

def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	odd = list([x for x in A if x % 2])
	even = list([x for x in A if x % 2 == 0])
	k = odd.count(1)
	res = None
	if k > 0:
		for i in even:
			if isprime[i + 1]:
				res = [1] * k + [i]
				return res
		if k > 1:
			res = [1] * k
			return res
	if res is None:
		for i in odd:
			for j in even:
				if isprime[i + j]:
					res = [i, j]
					return res
	return [A[0]]
res = solve()
print(len(res))
print(' '.join(map(str, res)))


n = int(input())
t = list(map(int, input().split()))
k = t.count(1)
s = ' '.join('1' * k)
p = [0] + [1, 0] * 1000000
for i in range(3, 1415, 2):
	if p[i]:
		p[i * i::2 * i] = [0] * ((2000000 - i * i) // 2 // i + 1)
if k > 1:
	for q in t:
		if q > 1 and p[1 + q]:
			exit(print(k + 1, q, s))
	exit(print(k, s))
for i in range(n):
	for j in range(i + 1, n):
		if p[t[i] + t[j]]:
			exit(print(2, t[i], t[j]))
print(1, t[0])