JOIN
Get Time

   Problem Statement  

 Problem Statement for PrimeAnagrams

Problem Statement

    

You will be given a string of digits that supposedly come from three prime numbers. The digits will be given in a random order. Your task is to find the three prime numbers, if they exist. If there are three such primes, return them sorted least to greatest. If there is more than one possible set of three primes, return the set with the smallest product. If there is no such set, return { }.

For example, the five digits of the primes 5, 13, and 19 could be given to you as "39151". There are several other sets of prime numbers that could also be rearranged to give this input, for example { 5, 31, 19 } and { 3, 11, 59 }. The set with the smallest product is { 5, 13, 19 }, so those are the three primes your method should return.

Each digit of each prime will be present in the input. For example, if the input contains exactly two occurrences of the digit "1" (as in the example above), you must use the digit "1" exactly twice.

Any zeros in the input may not be used as leading zeros in any of the three primes.

 

Definition

    
Class:PrimeAnagrams
Method:primes
Parameters:String
Returns:int[]
Method signature:int[] primes(String anagram)
(be sure your method is public)
    
 

Notes

-If you find two sets of primes with the same product, you have made a startling discovery!
 

Constraints

-anagram will contain between 3 and 8 characters, inclusive.
-Each character of anagram will be a digit.
 

Examples

0)
    
"39151"
Returns: { 5,  13,  19 }
This is the example from the problem statement.
1)
    
"921179"
Returns: { 2,  17,  199 }
2)
    
"01123"
Returns: { 2,  3,  101 }
The input may have a leading zero, but the primes may not. {2, 3, 011} is not a valid answer.
3)
    
"0707070"
Returns: { }
4)
    
"222"
Returns: { 2,  2,  2 }
5)
    
"123"
Returns: { }
1 is not prime.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 223 Round 1 - Division I, Level Two
       Single Round Match 223 Round 1 - Division II, Level Three