Largest component size in a graph formed by connecting non | Java program to implement the above approach ; 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
import java . util . * ; class GFG { static int [ ] spf = new int [ 100005 ] ; static 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 ; } } } } static void factorize ( int n , HashSet < Integer > s ) { while ( n > 1 ) { int z = spf [ n ] ; s . add ( z ) ; while ( n % z == 0 ) n /= z ; } } static int [ ] id = new int [ 100005 ] ; static int [ ] par = new int [ 100005 ] ; static int [ ] sizeContainer = new int [ 100005 ] ; static int root ( int i ) { if ( par [ i ] == i ) return i ; else return par [ i ] = root ( par [ i ] ) ; } static void merge ( int a , int b ) { int p = root ( a ) ; int q = root ( b ) ; if ( p == q ) return ; if ( sizeContainer [ p ] > sizeContainer [ q ] ) { p = p + q ; q = p - q ; p = p - q ; } par [ p ] = q ; sizeContainer [ q ] += sizeContainer [ p ] ; } static 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 ++ ) { HashSet < Integer > s = new HashSet < Integer > ( ) ; factorize ( a [ i ] , s ) ; for ( int 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 = Math . max ( answer , sizeContainer [ i ] ) ; return answer ; } public static void main ( String [ ] args ) { int n = 8 ; int A [ ] = { 2 , 3 , 6 , 7 , 4 , 12 , 21 , 39 } ; System . out . print ( maximumComponentsizeContainer ( A , n ) ) ; } }