A machine has n gears, each labeled with its tooth count (an integer at least 2). Two gears mesh directly if their tooth counts share a common factor greater than 1. Meshing is transitive: gears connected through a chain of meshing gears form one meshed group.
Report the number of gears in the largest meshed group.
n, the number of gears.n space-separated integers, the tooth counts. Values may repeat.A single integer: the size of the largest meshed group.
Example 1
Input
6 6 10 15 7 49 11
Expected
3
Explanation
6, 10, 15 mesh through shared factors 2, 3, 5, forming a group of 3. 7 and 49 mesh through 7 (group of 2). 11 is alone. The largest group has 3 gears.
Example 2
Input
3 2 3 5
Expected
1
Explanation
2, 3, 5 are pairwise coprime, so no two mesh; the largest group is a single gear.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →