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?
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
[2357]|1.*[19]|(?:8.*8|9.*(?:0.*0|9)|[46]).*1|(?:4.*[049]|(?:6.*4|9.*4(?:.*6){2}).*6|(?:9.*[069]|6.*(?:(?:0.*0|6.*[06])(?:.*0){3}|(?:6.*6|0).*6|9)).*4|8).*9
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.
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.
Well, I think you'd need to set some sort of limitations on the size of the integer and the size of the prime, but one thought would be to break up the digits into an array of powers of 10, then you could take each of your primes, and do a search by taking each n-digit prime, comparing it to the low order n-digits and, if no match is found, shifting one digit (e.g. power of 10) to the left.
Another thought would be to generate a list of all primes up to n digits (where n is the number of digits in the the largest prime you will be checking against), then, after breaking up the integer into powers of 10, for each number of digits between 1 and n generate a list of permutations of n-digit-integers and compare by searching your list of all primes up to n digits.
The efficiency I am probably not the best to speak to, but I think there will be a lot of dependencies even on the limitations (or not) we can set on it ahead of time: e.g. are the primes pre-generated, what is the maximum number of digits in the integer or max prime to be searched. (I think the problem becomes intractable more quickly as the ratio of prime digits to integer digits approaches 1.) I also think that the most efficient algorithm in any of those cases may radically differ from one another. If this is for a general algorithm with no particular limitations, then it's very possible that the most efficient algorithm differs from the particular cases.
Found the solution for your question!
An integer does not have a non-single-digit prime number in it as a subsequence (may be non-contiguous) if and only if this integer when removing all trailing digits 0, 2, 4, 5, 6, 8, the remaining number is of one of these forms:
