$1$

Let $d=($:$d_1,$dots,$d_n$:$)$ be a sequence of $n$ decimal digits. We want to determine, whether $d$ can be seen as the concatenation of the decimal representation of a sequence of prime numbers. Let us call such a sequence primey.

So the sequence $17257191009$ is primey since it can be written as $17$ followed by $257$ followed by $19$ followed by $1009,$ each of which is the $($usual$)$ decimal representation of a prime number.

However the sequence $17257191006$ is definitely not primey since in decimal representation no prime ends in digit $6$ and therefore there is no possible last "prime" part in any concatenation.

What about the sequence $17267191009?$

Develop an algorithm for testing whether a given sequence of decimal digits $d[1..n]$ is primey. Assume you have a function isprime $(i,j)$ available that magically tells in constant time whether the subsequence $d[i..j]$ is the decimal representation of a prime number $($with $1ijn).$ Your algorithm should run in polynomial time.