maksyuki 发表于 oj 分类,标签:

Digit Primes

A prime number is a positive number, which is divisible by exactly two different integers. A digit prime is a prime number whose sum of digits is also prime. For example the prime number 41 is a digit prime
because 4+1=5 and 5 is a prime number. 17 is not a digit prime because 1+7 = 8, and 8 is not a prime number. In this problem your job is to find out the number of digit primes
within a certain range less than 1000000.


First line of the input file contains a single integer N (0<N<=500000) that indicates the total number of inputs. Each of the next N lines contains two integers t1 and t2 (0<t1<=t2<1000000).


For each line of input except the first line produce one line of output containing a single integer that indicates the number of digit primes between t1 and t2 (inclusive).

Sample Input

310 2010 100100 10000 110576



算法分析:首先使用Euler筛将2至1000000之间的所有的素数筛出来,然后从小到大判断所有的素数val的位数字之和是否为素数,如果是则将OK[val] = 1,然后将OK构建成一个前缀表,之后对于每一个查询直接求相应数的前缀差即可