2009 Mock DWITE by A.J.: Problem 2

The Missing Link...

Having just learned what primes are in math class, Boxer wants to put this newly acquired skill to the test. Given a number that is missing a digit, help Boxer list all possible digits that makes this number prime.

Input

The input will contain five lines, each containing a string of characters which consists of up to 6 characters. Exactly one of these characters will be an underscore ('_'), while the rest will be digits. The first character in the string will never be the digit zero. This string represents an integer with one missing digit. (The missing digit is represented by the underscore.)

Output

For each line given in input, in the order given, print one line containing a space-separated list of digits sorted in ascending order which can be used to fill in the blank for the missing digit such that the number generated is prime, or the string Not possible if there is no digit which fulfils the requirement.

Sample Input (only three sets shown)

1_
32_23
_46230

Sample Output

1 3 7 9
3 4
Not possible

Explanation

In the first case, there are four primes that can be obtained by filling in the blank: 11, 13, 17, and 19, obtained by filling in the blank with the digits 1, 3, 7, and 9, respectively.

In the second case, there are two five-digit primes starting with 32 and ending with 23, and they are 32323 and 32423, obtained by filling in the blank with 3 and 4, respectively.

In the third case, regardless of the digit filling the blank, 2 will be a proper factor, so no choice yields a prime number.

All Submissions
Best Solutions


Point Value: 7
Time Limit: 5.00s
Memory Limit: 256M
Added: Sep 26, 2009
Author: amleshjk

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Can the first character be '0'?

The first character in the string will never be the digit zero.
In addition, I looked through accepted solutions and it looks like you can assume you're not allowed to fill in the blank with zero if it occurs in the leftmost column, either.