Largest Component Size by Common Factor

Given an array of positive integers, connect two numbers if they share a common factor greater than 1, and return the size of the largest connected component. This problem uses DSU find logic over factor-based connectivity.

Input Format

nums = array of positive integers

Output Format

size of the largest connected component

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

nums = [4,6,15,35]

Output:

4

Explanation:

All four numbers are connected through shared factors.

Example 2:

Input:

nums = [20,50,9,63]

Output:

2

Explanation:

The component {20,50} has size 2 and {9,63} has size 2.

Example 3:

Input:

nums = [2,3,6,7,4,12,21,39]

Output:

8

Explanation:

All numbers except 7 become connected through shared factors.

Loading...
Largest Component Size by Common Factor