999. The Largest Group Sharing a Factor

You are given n distinct positive integers. Two of them are DIRECTLY related when they share a common factor greater than 1, and the relation is passed along: if a is related to b and b to c, all three are in one group even when a and c share nothing.

Print the number of values in the largest group.

4 6 15 35 -> 4 4 and 6 share 2, 6 and 15 share 3, 15 and 35 share 5 2 3 5 -> 1 three primes, nothing shared 1 2 4 8 -> 3 1 shares no factor above 1 with anything, not even itself 9 25 49 121 -> 1 four squares of four different primes 30 7 14 5 11 -> 4 30, 14, 7 and 5 join up, 11 stays out

## What most people try first

Take the greatest common divisor of every pair and join the ones above 1. That is n(n-1)/2 calls, which at n = 20000 is about 2 * 10^8 divisions with a logarithmic factor on top of each. It is also more work than the question needs, because the pair test throws away WHICH factor was shared.

## Join through the primes instead of through the pairs

Two numbers share a factor above 1 exactly when they share a PRIME factor. So give every prime its own element in the structure, alongside the n values, and union each value with each of its distinct prime factors:

sieve the smallest prime factor of every number up to max(a) for each index i with value v: while v > 1: p = smallestPrimeFactor[v] union(value node i, prime node p) while v is divisible by p: v = v / p

A value has at most 6 distinct prime factors below 10^5, since 2 * 3 * 5 * 7 * 11 * 13 = 30030 and adding 17 passes 10^5, so the whole loop is at most 6n unions.

## Why this gives the same groups

If two values share a prime p they are both joined to p's element, so they land in one group. Going the other way, a union is only ever made between a value and one of its own primes, so any two values in one group are linked by an alternating chain of values and primes, and each consecutive value pair in that chain shares the prime between them. That is exactly a chain of direct relations.

## The counting trap

The structure now holds value elements AND prime elements, and only the values are being counted. A group made of 3 values and 4 primes has 7 elements and must report 3. Count by walking the n value indices and tallying their roots, never by reading a size array that includes the primes.

## The value 1

It has no prime factors at all, so the loop does not run and it stays alone. It is not related to itself either: the relation needs a shared factor ABOVE 1, and gcd(1, 1) is 1. The third example answers 3 rather than 4 for that reason.

## Overflow

Values stop at 10^5 and n at 2 * 10^4, so every quantity here is far inside a signed 32 bit integer. The sieve array is 10^5 + 1 entries, which is small.

## Cross-reference

Problem 1033 joins numbers through their divisors too, but from the other end: it sweeps each divisor above a threshold and unions its multiples, which needs no factorisation at all. Problem 989 uses the same idea of a shared KEY with a hash map of tags rather than a table of primes.

## Cost

Time O(max(a) log log max(a)) for the sieve plus O(n * 6 * alpha) for the unions. Space O(max(a) + n).

Constraints - `1 ≤ n ≤ 20000` - `1 ≤ a[i] ≤ 100000` - The values are distinct.