Largest component size in a graph formed by connecting non |  ; smallest prime factor ; Sieve of Eratosthenes ; is spf [ i ] = 0 , then it 's prime ; smallest prime factor of all multiples is i ; Prime factorise n , and store prime factors in set s ; for implementing DSU ; root of component of node i ; finding root as well as applying path compression ; merging two components ; find roots of both components ; if already belonging to the same compenent ; Union by rank , the rank in this case is sizeContainer of the component . Smaller sizeContainer will be merged into larger , so the larger 's root will be  final root ; Function to find the maximum sized container ; intitalise the parents , and component sizeContainer ; intitally all component sizeContainers are 1 ans each node it parent of itself ; store prime factors of a [ i ] in s ; if this prime is seen as a factor for the first time ; if not then merge with that component in which this prime was previously seen ; maximum of sizeContainer of all components ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int spf [ 100005 ] ; void sieve ( ) { for ( int i = 2 ; i < 100005 ; i ++ ) { if ( spf [ i ] == 0 ) { spf [ i ] = i ; for ( int j = 2 * i ; j < 100005 ; j += i ) { if ( spf [ j ] == 0 ) spf [ j ] = i ; } } } } void factorize ( int n , set < int > & s ) { while ( n > 1 ) { int z = spf [ n ] ; s . insert ( z ) ; while ( n % z == 0 ) n /= z ; } } int id [ 100005 ] ; int par [ 100005 ] ; int sizeContainer [ 100005 ] ; int root ( int i ) { if ( par [ i ] == i ) return i ; else return par [ i ] = root ( par [ i ] ) ; } void merge ( int a , int b ) { int p = root ( a ) ; int q = root ( b ) ; if ( p == q ) return ; if ( sizeContainer [ p ] > sizeContainer [ q ] ) swap ( p , q ) ; par [ p ] = q ; sizeContainer [ q ] += sizeContainer [ p ] ; } int maximumComponentsizeContainer ( int a [ ] , int n ) { for ( int i = 0 ; i < 100005 ; i ++ ) { par [ i ] = i ; sizeContainer [ i ] = 1 ; } sieve ( ) ; for ( int i = 0 ; i < n ; i ++ ) { set < int > s ; factorize ( a [ i ] , s ) ; for ( auto it : s ) { if ( id [ it ] == 0 ) id [ it ] = i + 1 ; else merge ( i + 1 , id [ it ] ) ; } } int answer = 0 ; for ( int i = 0 ; i < n ; i ++ ) answer = max ( answer , sizeContainer [ i ] ) ; return answer ; } int main ( ) { int n = 8 ; int A [ ] = { 2 , 3 , 6 , 7 , 4 , 12 , 21 , 39 } ; cout << maximumComponentsizeContainer ( A , n ) ; return 0 ; }