AtCoder Regular Contest 080 - Prime Flip

There are infinitely many cards, numbered 1, 2, 3, ...
Initially, Cards x_1, x_2, ..., x_N are face up, and the others are face down.
Snuke can perform the following operation repeatedly:
 - Select a prime p greater than or equal to 3. Then, select p consecutive cards and flip all of them.
Snuke's objective is to have all the cards face down.
Find the minimum number of operations required to achieve the objective.

-----Constraints-----
 - 1 ≤ N ≤ 100
 - 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 x_2 ... x_N

-----Output-----
Print the minimum number of operations required to achieve the objective.

-----Sample Input-----
2
4 5

-----Sample Output-----
2

Below is one way to achieve the objective in two operations:
 - Select p = 5 and flip Cards 1, 2, 3, 4 and 5.
 - Select p = 3 and flip Cards 1, 2 and 3.

Source: atcoder | Difficulty: VERY_HARD


Solutions:
import sys
input = sys.stdin.readline
import itertools
from collections import defaultdict
import numpy as np
N = int(input())
X = set((int(x) for x in input().split()))
U = 10 ** 7 + 100
is_prime = np.zeros(U, dtype=np.bool)
is_prime[3::2] = 1
for p in range(3, U, 2):
	if p * p > U:
		break
	if is_prime[p]:
		is_prime[p * p::p + p] = 0
X ^= set((x + 1 for x in X))
EV = set((x for x in X if x % 2 == 0))
OD = set((x for x in X if x % 2 == 1))
source = -1
sink = -2
graph = defaultdict(dict)
for x in EV:
	graph[x][sink] = 1
	graph[sink][x] = 0
for x in OD:
	graph[source][x] = 1
	graph[x][source] = 0
for (x, y) in itertools.product(OD, EV):
	if is_prime[abs(x - y)]:
		graph[x][y] = 1
		graph[y][x] = 0

def bfs():
	level = defaultdict(int)
	q = [source]
	level[source] = 1
	d = 1
	while q:
		d += 1
		if level[sink] != 0:
			break
		qq = []
		for x in q:
			for (y, cap) in graph[x].items():
				if cap == 0 or level[y] != 0:
					continue
				level[y] = d
				qq.append(y)
		q = qq
	return level

def dfs(v, f, level, itr):
	if v == sink:
		return f
	for (w, cap) in itr[v]:
		if cap == 0 or level[w] != level[v] + 1:
			continue
		d = dfs(w, min(f, cap), level, itr)
		if d:
			graph[v][w] -= d
			graph[w][v] += d
			return d
	return 0

def max_flow():
	flow = 0
	while True:
		level = bfs()
		if level[sink] == 0:
			return flow
		itr = {v: iter(graph[v].items()) for v in graph}
		while True:
			f = dfs(source, 10 ** 9, level, itr)
			if f == 0:
				break
			flow += f
f = max_flow()
od = len(OD)
ev = len(EV)
answer = f
od -= f
ev -= f
answer += 2 * (od // 2)
od %= 2
answer += 2 * (ev // 2)
ev %= 2
if od:
	answer += 3
print(answer)


import itertools
from math import sqrt

def chunk(a):
	i = 0
	res = []
	while i < len(a):
		res.append(a[i])
		while i != len(a) - 1 and a[i + 1] == a[i] + 1:
			i += 1
		res.append(a[i] + 1)
		i += 1
	return res

def augment(g, src, dest):
	o = [None] * len(g)
	q = [(src, src)]
	while q:
		w = q.pop()
		if o[w[0]] is None:
			o[w[0]] = w[1]
			for s in g[w[0]]:
				if o[s] is None:
					q.append((s, w[0]))
	if not o[dest]:
		return False
	i = dest
	while i != src:
		g[o[i]].discard(i)
		g[i].add(o[i])
		i = o[i]
	return True

def match(a):
	l = {}
	c = 0
	matches = 0
	for (i, j) in a:
		if i not in l:
			l[i] = c
			c += 1
		if j not in l:
			l[j] = c
			c += 1
	L = {v: k for (k, v) in l.items()}
	g = [set() for i in range(len(l) + 2)]
	src = len(l)
	dest = src + 1
	for (i, j) in a:
		g[src].add(l[i])
		g[l[i]].add(l[j])
		g[l[j]].add(dest)
	while augment(g, src, dest):
		matches += 1
	return matches

def prime(n):
	for i in range(2, min(n, int(sqrt(n) + 7))):
		if n % i == 0:
			return False
	return n > 1

def pairs(b):
	c = []
	for i in b:
		for j in b:
			if i % 2 == 0 and j % 2 == 1 and prime(abs(i - j)):
				c.append((i, j))
	return c
n = int(input())
a = list(map(int, input().split()))
b = chunk(a)
r = match(pairs(b))
e = len(list(filter(lambda x: x % 2 == 0, b)))
o = len(b) - e
print(int(r + 2 * ((e - r) // 2 + (o - r) // 2) + 3 * ((e - r) % 2)))