分数: 1200 点
问题陈述
有无限张牌,编号为 1, 2, 3, ... 最初,卡片 x_1, x_2, ..., x_N 面朝上,其他面朝下。
Snuke可以重复执行以下操作:
- 选择一个素数 p 大于或等于 3。然后,选择 p 连续的牌并将其全部翻转。
Snuke 的目标是让所有牌面朝下。 找出实现目标所需的最少操作次数。
约束
- 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