/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1200 点
問題文
無限枚のカードがあります。 カードには 1, 2, 3, ... と番号が振られています。 最初、カード x_1, x_2, ..., x_N は表向きで、それら以外のカードは裏向きです。
すぬけ君は次の操作を繰り返し行うことができます。
- 3 以上の素数 p を選ぶ。 番号が連続する p 枚のカードを選び、それらすべてをひっくり返す。
すぬけ君の目標は、すべてのカードを裏向きにすることです。 すぬけ君が目標を達成するために必要な操作回数の最小値を求めてください。
制約
- 1 ≤ N ≤ 100
- 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7
入力
入力は以下の形式で標準入力から与えられる。
N x_1 x_2 ... x_N
出力
すぬけ君が目標を達成するために必要な操作回数の最小値を出力せよ。
入力例 1
2 4 5
出力例 1
2
例えば、次の順に操作を行えばよいです。
- p = 5 を選び、カード 1, 2, 3, 4, 5 をひっくり返す。
- p = 3 を選び、カード 1, 2, 3 をひっくり返す。
入力例 2
9 1 2 3 4 5 6 7 8 9
出力例 2
3
例えば、次の順に操作を行えばよいです。
- p = 3 を選び、カード 1, 2, 3 をひっくり返す。
- p = 3 を選び、カード 4, 5, 6 をひっくり返す。
- p = 3 を選び、カード 7, 8, 9 をひっくり返す。
入力例 3
2 1 10000000
出力例 3
4
Score : 1200 points
Problem Statement
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 1
2 4 5
Sample Output 1
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.
Sample Input 2
9 1 2 3 4 5 6 7 8 9
Sample Output 2
3
Below is one way to achieve the objective in three operations:
- Select p = 3 and flip Cards 1, 2 and 3.
- Select p = 3 and flip Cards 4, 5 and 6.
- Select p = 3 and flip Cards 7, 8 and 9.
Sample Input 3
2 1 10000000
Sample Output 3
4