1using System;
2using System.Collections.Generic;
3
4public class UnionFind {
5    private int[] parent;
6    private int[] size;
7
8    public UnionFind(int n) {
9        parent = new int[n];
10        size = new int[n];
11        for (int i = 0; i < n; i++) {
12            parent[i] = i;
13            size[i] = 1;
14        }
    }

    public int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    public void Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    }

    public int GetSize(int x) {
        return size[Find(x)];
    }
}

public class Solution {
    public int LargestComponentSize(int[] nums) {
        int maxNum = 0;
        foreach (int num in nums) {
            if (num > maxNum) maxNum = num;
        }

        UnionFind uf = new UnionFind(maxNum + 1);

        foreach (int num in nums) {
            for (int factor = 2; factor <= Math.Sqrt(num); factor++) {
                if (num % factor == 0) {
                    uf.Union(num, factor);
                    uf.Union(num, num / factor);
                }
            }
        }

        Dictionary<int, int> count = new Dictionary<int, int>();
        int result = 0;

        foreach (int num in nums) {
            int root = uf.Find(num);
            if (!count.ContainsKey(root)) count[root] = 0;
            count[root]++;
            if (count[root] > result) result = count[root];
        }

        return result;
    }

    // Example usage:
    public static void Main() {
        int[] nums = {4, 6, 15, 35};
        Solution solution = new Solution();
        Console.WriteLine(solution.LargestComponentSize(nums)); // Output: 4
    }
}