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
var spf = Array ( 100005 ) . fill ( 0 ) ; function sieve ( ) { for ( var i = 2 ; i < 100005 ; i ++ ) { if ( spf [ i ] == 0 ) { spf [ i ] = i ; for ( var j = 2 * i ; j < 100005 ; j += i ) { if ( spf [ j ] == 0 ) spf [ j ] = i ; } } } } function factorize ( n , s ) { while ( n > 1 ) { var z = spf [ n ] ; s . add ( z ) ; while ( n % z == 0 ) n = parseInt ( n / z ) ; } return s ; } var id = Array ( 100005 ) . fill ( 0 ) ; var par = Array ( 100005 ) . fill ( 0 ) ; var sizeContainer = Array ( 100005 ) . fill ( 0 ) ; function root ( i ) { if ( par [ i ] == i ) return i ; else return par [ i ] = root ( par [ i ] ) ; } function merge ( a , b ) { var p = root ( a ) ; var q = root ( b ) ; if ( p == q ) return ; if ( sizeContainer [ p ] > sizeContainer [ q ] ) { [ p , q ] = [ q , p ] } par [ p ] = q ; sizeContainer [ q ] += sizeContainer [ p ] ; } function maximumComponentsizeContainer ( a , n ) { for ( var i = 0 ; i < 100005 ; i ++ ) { par [ i ] = i ; sizeContainer [ i ] = 1 ; } sieve ( ) ; for ( var i = 0 ; i < n ; i ++ ) { var s = new Set ( ) ; s = factorize ( a [ i ] , s ) ; s . forEach ( it => { if ( id [ it ] == 0 ) id [ it ] = i + 1 ; else merge ( i + 1 , id [ it ] ) ; } ) ; } var answer = 0 ; for ( var i = 0 ; i < n ; i ++ ) answer = Math . max ( answer , sizeContainer [ i ] ) ; return answer ; } var n = 8 ; var A = [ 2 , 3 , 6 , 7 , 4 , 12 , 21 , 39 ] ; document . write ( maximumComponentsizeContainer ( A , n ) ) ;