There is a solution that would take O(n):
Let our numbers be a_i
. First, calculate m=a_0*a_1*a_2*...
. For each number a_i, calculate gcd(m/a_i, a_i)
. The number you are looking for is the maximum of these values.
I haven't proved that this is always true, but in your example, it works:
m=2*4*5*15=600,
max(gcd(m/2,2), gcd(m/4,4), gcd(m/5,5), gcd(m/15,15))=max(2, 2, 5, 5)=5
NOTE: This is not correct. If the number a_i
has a factor p_j
repeated twice, and if two other numbers also contain this factor, p_j
, then you get the incorrect result p_j^2
insted of p_j
. For example, for the set 3, 5, 15, 25
, you get 25
as the answer instead of 5
.
However, you can still use this to quickly filter out numbers. For example, in the above case, once you determine the 25, you can first do the exhaustive search for a_3=25
with gcd(a_3, a_i)
to find the real maximum, 5
, then filter out gcd(m/a_i, a_i), i!=3
which are less than or equal to 5
(in the example above, this filters out all others).
Added for clarification and justification:
To see why this should work, note that gcd(a_i, a_j)
divides gcd(m/a_i, a_i)
for all j!=i
.
Let's call gcd(m/a_i, a_i)
as g_i
, and max(gcd(a_i, a_j),j=1..n, j!=i)
as r_i
. What I say above is g_i=x_i*r_i
, and x_i
is an integer. It is obvious that r_i <= g_i
, so in n
gcd operations, we get an upper bound for r_i
for all i
.
The above claim is not very obvious. Let's examine it a bit deeper to see why it is true: the gcd of a_i
and a_j
is the product of all prime factors that appear in both a_i
and a_j
(by definition). Now, multiply a_j
with another number, b
. The gcd of a_i
and b*a_j
is either equal to gcd(a_i, a_j)
, or is a multiple of it, because b*a_j
contains all prime factors of a_j
, and some more prime factors contributed by b
, which may also be included in the factorization of a_i
. In fact, gcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j)
, I think. But I can't see a way to make use of this. :)
Anyhow, in our construction, m/a_i
is simply a shortcut to calculate the product of all a_j
, where j=1..1, j!=i
. As a result, gcd(m/a_i, a_i)
contains all gcd(a_i, a_j)
as a factor. So, obviously, the maximum of these individual gcd results will divide g_i
.
Now, the largest g_i
is of particular interest to us: it is either the maximum gcd itself (if x_i
is 1), or a good candidate for being one. To do that, we do another n-1
gcd operations, and calculate r_i
explicitly. Then, we drop all g_j
less than or equal to r_i
as candidates. If we don't have any other candidate left, we are done. If not, we pick up the next largest g_k
, and calculate r_k
. If r_k <= r_i
, we drop g_k
, and repeat with another g_k'
. If r_k > r_i
, we filter out remaining g_j <= r_k
, and repeat.
I think it is possible to construct a number set that will make this algorithm run in O(n^2) (if we fail to filter out anything), but on random number sets, I think it will quickly get rid of large chunks of candidates.