O(nlg(n))  FULL SOLUTION WITH EXPLANATION
since the maximum value of n<=100000, which means our solution must have atmost \nT(n)<=O(nlg(n).\nThe main crux of problem is to connect the two number having 
since the maximum value of n<=100000, which means our solution must have atmost \nT(n)<=O(nlg(n).\nThe main crux of problem is to connect the two number having a divisor greater than 1.\nAgain we know every number  can we written as multiple of prime numbers (prime factorisation).\nWe will use sieve ***REFER*** [https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/](http://)\nI will tell anyway the psudo code of prime factorisation\nprime_fact(n):\nwhile(n%2==0):\nn=n/2;        // 2 is prime factor\nfor(i=3;i<=sqrt(n);i++):\n\twhile(n%i):\n\t\tn=n/i;  // 3 is prime factor\nif(n>2): \nn                // n is primefacor\n\nWe will use MAP to store mapping from prime number to respective index.\nThen will use Disjoint Union Find Data Structure with path compression  ***REFER***\n[https://drive.google.com/file/d/1Zky8tK6GKRcoLUZMFdxqsEF0hTFSm1Pn/view?usp=sharing]\n\n\n```\nint find_root(vector<int>&id,int i){\n    while(i!=id[i]){\n        id[i]=id[id[i]]; //pathcompression;\n        i=id[i];\n    }\n    return i;\n}\n\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& A) {\n        map<int,vector<int>>mymap;\n        vector<int>id(A.size());\n        vector<int>size(A.size(),1);\n        for(int i=0;i<A.size();i++){\n            id[i]=i;\n        }\n           \n        int n;\n        \n        for(int i=0;i<A.size();i++){\n            n=A[i];\n            bool temp=false;\n            while(n%2==0){\n                n=n/2;\n                temp=true;\n             }\n            if(temp==true) mymap[2].push_back(i);\n            for(int k=3;k<=sqrt(n);k++){\n                \n                temp=false;\n                while(n%k==0){\n                    n=n/k;\n                    temp=true;\n                }\n                \n                if(temp==true) mymap[k].push_back(i);\n            }\n            \n            if(n>2){\n                mymap[n].push_back(i);\n            }\n            \n        }\n        \n        int maxi=1;\n        \n        for(auto it=mymap.begin();it!=mymap.end();it++){\n            \n            for(int k=0;k<it->second.size()-1;k++){\n                int pa=find_root(id,it->second[k]);\n                int pb=find_root(id,it->second[k+1]);\n                if(pa!=pb){\n                    \n                    if(size[pa]>size[pb]){\n                        id[pb]=pa;\n                        size[pa]+=size[pb];\n                        maxi=max(maxi,size[pa]);\n                    }\n                    else{\n                        id[pa]=pb;\n                        size[pb]+=size[pa];\n                        maxi=max(maxi,size[pb]);\n                    }\n                    \n                }\n                  \n            }\n            \n        }\n        return maxi;   \n    }\n};\n```\n
[]