Is there any way by which one can check if an integer has a prime number as a subsequence (may be non-contiguous)?
We can check if they contain the digits 2,3,5 or 7 by going through the digits, but how to check if they contain 11, 13,… ?
One way would be to convert each number to a string and then call contains function, but that may be too expensive for a large range of numbers.
Any other efficient way?
Best Answer
This can be tested efficiently due to a theorem of Shallit, which builds on a classical result on combinatorics on words:
Every prime has one of 2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, and 66600049 (Sloane's A071062) as a subsequence of its decimal digits.
To implement efficiently, I would suggest making an array of permissible 3-digit sequences and reducing mod 1000 (perhaps repeatedly, if testing shows it to be efficient). If you get a hit, you can short-circuit and return "true". Otherwise, convert the number to a string and use a standard regular expression library to efficiently test if
matches your number. This should take time linear in the length of the input number, both for conversion (if using an efficient algorithm) and regex testing (if using an efficient algorithm with regex preprocessing).
If you check the whole number in 1000-digit increments you can leave off the testing of the one-digit numbers.