1052. Largest Component Size by Common Factor

Given an array of distinct positive integers 'nums', build a graph where two numbers are connected if they share a common factor greater than 1. Return the size of the largest connected component. The input is JSON {nums}.

Input: JSON {nums}.

Output: Integer — the largest component size.

Examples

Input: {"nums":[4,6,15,35]}
Output: 4
Explanation: All connect through shared factors.

Input: {"nums":[20,50,9,63]}
Output: 2
Explanation: Two pairs of size 2.

Input: {"nums":[2,3,6,7,4,12,21,39]}
Output: 8
Explanation: All in one component.

Constraints

• 1<=nums<=2*10^4
• 1<=value<=10^5
• distinct

Asked by