#XMOJ12793. 素数部分列
素数部分列
说明
时间限制:1 Sec
内存限制:256 MB
输入文件:prime.in 输出文件:prime.out
有一个由字符 1、3、5、7、9 构成的长度为 $N$ 的字符串 $S$。
你可以重复执行下面的操作,希望最大化操作次数:
- 选出 $S$ 的一个部分列(不需要连续),把这个部分列视作一个整数,若该整数是素数,则删除这个部分列。
求最多可以进行多少次操作。输入格式
第一行一个整数 $N$。
第二行一个字符串 $S$。
输出格式
输出一行一个整数,表示答案。
样例
样例 1
6
993711
3
样例说明:
一种可行操作如下:
$9\underline{9}3\underline{7}11 \rightarrow 9\underline{3}11 \rightarrow 9\underline{11} \rightarrow 9$
下划线为每次选中的部分列。
$97,3,11$ 都是素数。
样例 2
5
99999
0
样例说明:
不存在可以作为素数的部分列,一次操作都无法执行。
样例 3
4
1333
3
数据范围
对于 20% 的数据,$N \le 50$。
对于 100% 的数据,$1 \le N \le 2\times 10^5$,$S$ 仅由 1、3、5、7、9 组成。
相关
在下列比赛中: