AtCoder Regular Contest 080

F - Prime Flip


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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

Submit提出する