TopCoder problem "CommonFactors" used in TCHS SRM 48 (Division I Level Two)



Problem Statement

    

You are given a list of numbers in a int[] n. A number k is a factor of number m if m can be exactly divided into k. Find the factor greater than 1 that is shared by the most elements in n. If there are several such factors, return the largest one among them.

 

Definition

    
Class:CommonFactors
Method:mostCommon
Parameters:int[]
Returns:int
Method signature:int mostCommon(int[] n)
(be sure your method is public)
    
 

Constraints

-n will contain between 1 and 50 elements, inclusive.
-Each element of n will be between 2 and 1000000000, inclusive.
 

Examples

0)
    
{2, 3, 4, 6}
Returns: 2
2 is a factor of 3 elements of n (2, 4 and 6). 3 is a factor of two elements (3 and 6). 4 and 6 are not factors of any numbers except themselves.
1)
    
{2, 3, 6}
Returns: 3
Both 2 and 3 are factors of exactly two numbers. Based on the tie-breaker rule, we pick the larger.
2)
    
{2, 3, 5, 7}
Returns: 7
No factor appears more than once, so again we use the tie-breaker rule.
3)
    
{2, 3, 5, 6, 7, 9, 11, 12}
Returns: 3
4)
    
{24, 12, 37, 18, 11}
Returns: 6
5)
    
{3, 49, 7, 100, 100}
Returns: 100
6)
    
{123456789, 987654321, 246813579, 975318642}
Returns: 9
7)
    
{1000000000, 999999999, 999999999}
Returns: 999999999

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8140

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10807&pm=8140

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Simple Math