This looks like a homework problem. A hint (hint #1): one way to answer this is to find methods for generating sequences that do not have prime subsequences. You see how to eliminate numbers with 2, 3, 5, 7. That leaves the numbers 0, 1, 4, 6, 8, and 9. Since the prime subsequences may be non-contiguous, then a 1 preceded by a 1, 4, or 6 will nix that number. If there is a 9, then any preceding 1 or 8 will nix the number.
The trivial sequences are any resamplings solely of 4, 6, 8, and 0.
So, look at what sequences you can generate with a 1 or 9 preceded by some of these #s. Assume that the following (trailing #s) are composite (e.g. a sequence of even #s), so you're looking for the longest sequence of composite #s ending in 1 or 9 and preceded by 4, 6, 8, and 0.
Hint #2: in a sense you're looking to create a variation on the Sieve of Eratosthenes.
Hint #3: 6 is nice because it's divisible by 3. 4 and 8 in a pair also guarantee divisibility by 3. So, 9 will be a little harder to kill off than the 1. (Update / side note: 6 is almost ideal among the 10 digits for a default value a "trivial" sequence - it is composite & it does nothing to affect divisibility mod 3.)
Hint #4: I'll kill 1 for you: if it is preceded by a 4, then you get a prime. Preceded by a 6: you get a prime. Preceded by 1 8: not a prime. Preceded by 2 8s: 881 is prime. So, the number 1 is killed.
Okay, now try to kill the # 9.
Hint #5: If you can't kill off a # (i.e. the # 9), then it implies there is a trivial sequence that precedes it.
These 5 hints plus a short table of primes (e.g. http://primes.utm.edu/lists/small/1000.txt) should be adequate to solve the problem entirely.