> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Largest Component Size by Common Factor

> Tested Python solution for LeetCode 952 with 21 pytest cases. Generate a practice environment with lcpy.

LeetCode 952, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [Math](/catalog/topics/math), [Union-Find](/catalog/topics/union-find), [Number Theory](/catalog/topics/number-theory), Prime Factorization. [View on LeetCode](https://leetcode.com/problems/largest-component-size-by-common-factor/description/).

Generate this problem as a practice environment: tested reference solution, 21 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 952   # by problem number
lcpy gen -s largest_component_size_by_common_factor   # by problem name
```

## Problem

Given an integer array of unique positive integers `nums`. Consider the following graph:

* There are `nums.length` nodes, labeled `nums[0]` to `nums[nums.length - 1]`,
* There is an undirected edge between `nums[i]` and `nums[j]` if `nums[i]` and `nums[j]` share a common factor greater than `1`.

Return the size of the largest connected component in the graph.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2018/12/01/ex1.png)

```
Input: nums = [4,6,15,35]
Output: 4
```

![Example 2](https://assets.leetcode.com/uploads/2018/12/01/ex2.png)

```
Input: nums = [20,50,9,63]
Output: 2
```

![Example 3](https://assets.leetcode.com/uploads/2018/12/01/ex3.png)

```
Input: nums = [2,3,6,7,4,12,21,39]
Output: 8
```

### Constraints

* 1 \<= nums.length \<= 2 \* 10^4
* 1 \<= nums\[i] \<= 10^5
* All the values of nums are unique.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/largest_component_size_by_common_factor/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/largest_component_size_by_common_factor/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n * sqrt(max(nums)) * alpha(n))
    # Space: O(max(nums))
    def largest_component_size(self, nums: list[int]) -> int:
        parent: dict[int, int] = {}

        def find(x: int) -> int:
            root = x
            while parent[root] != root:
                root = parent[root]
            while parent[x] != root:
                parent[x], x = root, parent[x]
            return root

        def union(a: int, b: int) -> None:
            if b not in parent:
                parent[b] = b
            root_a, root_b = find(a), find(b)
            if root_a != root_b:
                parent[root_a] = root_b

        for num in nums:
            parent[num] = num

        for num in nums:
            reduced = num
            factor = 2
            while factor * factor <= reduced:
                if reduced % factor == 0:
                    union(num, factor)
                    while reduced % factor == 0:
                        reduced //= factor
                factor += 1
            if reduced > 1:
                union(num, reduced)

        sizes: dict[int, int] = {}
        largest = 0
        for num in nums:
            root = find(num)
            sizes[root] = sizes.get(root, 0) + 1
            largest = max(largest, sizes[root])
        return largest
```

## Complexity

| Time | Space |
| - | - |
| O(n \* sqrt(max(nums)) \* alpha(n)) | O(max(nums)) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.