Find the size of the largest connected component where two numbers are connected if they share a common factor greater than 1.
Problem
You are given an array of positive integers nums.
Build an undirected graph with one node per array element. Connect two nodes if the corresponding numbers have a common factor greater than 1.
Return the size of the largest connected component in this graph.
Two numbers belong to the same component if there is a path of edges between them, even if they are not directly connected.
Goal
Compute the maximum number of array elements that end up in any connected group.
Input Format
nums: an array of positive integers
Output Format
- Return an integer: the size of the largest connected component
Constraints
1 <= nums.length- All values are positive integers
- The intended solution should handle arrays with many numbers efficiently
Example 1
Input
nums = [4, 6, 15, 35]
Output
4
Explanation
- 4 and 6 share factor 2
- 6 and 15 share factor 3
- 15 and 35 share factor 5 All numbers become connected through a chain, so the largest component has size 4.
Example 2
Input
nums = [20, 50, 9, 63]
Output
2
Explanation
- 20 and 50 share factor 10
- 9 and 63 share factor 9 There are two separate components, each of size 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.