题目描述
小明对数的研究比较热爱,一谈到数,脑子里就涌现出好多数的问题,今天,小明想考考你对素数的认识。问题是这样的:一个十进制数,如果是素数,而且它的各位数字和也是素数,则称之为“美素数”,如29,本身是素数,而且2+9 = 11也是素数,所以它是美素数。给定一个区间,你能计算出这个区间内有多少个美素数吗?
输入描述
输入两个整数L,R(1<= L <= R <= 1000000),表示区间的左值和右值。
输出描述
输出区间内美素数的个数(包括端点值L,R)。
样例输入
1 100
样例输出
14
提示
使用素数筛法筛选出1000000以内的素数。然后,求出1000000以内符合条件的数字的个数,即满足自身是素数且各位数字和也是素数,累加,比如2是素数,则a[2] = 1;3是素数,则a[3] = a[2] + 1 = 2。最后,根据输入的L,R,直接输出a[R]-a[L-1]即可。