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.
InputThe 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.)
OutputFor 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 possibleif there is no digit which fulfils the requirement.
Sample Input (only three sets shown)
1_ 32_23 _46230
1 3 7 9 3 4 Not possible
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.
Point Value: 7
Time Limit: 5.00s
Memory Limit: 256M
Added: Sep 26, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3