Problem J
Subprime
There is an open math problem: Is every non-negative integer a substring of at least one prime number when expressed in base ten?
A positive integer is a prime number if it is greater than one and not a product of two smaller positive integers. Integer $a$ is a substring of integer $b$ if it is equal to an integer derived from $b$ by deleting zero or more consecutive digits of the most and least significant digits of $b$. For example, $123$ is a substring of: $\underline{123}, 56\underline{123}, \underline{123}789, 501823\underline{123}65, 4\underline{123}7912\underline{123}$.
Given two integers $l$ and $h$ along with an integer $p$, you are to check how many primes between the $l$th smallest prime and the $h$th smallest prime (both ends are inclusive) contain a substring that equals $p$. We are interested in substrings that may include significant leading zeroes, and thus $p$ may have leading zeroes. A prime shall be counted only once even if the integer $p$ occurs more than once as its substring.
For example, consider $l = 1, h = 10$ and $p = 9$. This is a search from the $1$st smallest prime ($2$) to the $10$th smallest prime ($29$) for any prime containing the substring “$9$”. There are $2$ such primes: $1\underline{9}$ and $2\underline{9}$.
Input
The first line of input has two integers $l$ and $h$ ($1 \leq l \leq h \leq 10^5$). The second line has a sequence of $1$ to $6$ digits giving the integer $p$, which may be zero or have significant leading zeroes.
Output
Output the count of prime numbers in the given range that contain $p$ as a substring.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 10 9 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
500 1000 43 |
26 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 1000 00 |
10 |
