How to check if an integer has a prime number in it?

Solution 1:

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.

Solution 2:

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.