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
spf = [ 0 for i in range ( 100005 ) ] NEW_LINE def sieve ( ) : NEW_LINE INDENT for i in range ( 2 , 100005 ) : NEW_LINE INDENT if ( spf [ i ] == 0 ) : NEW_LINE INDENT spf [ i ] = i ; NEW_LINE for j in range ( 2 * i , 100005 , i ) : NEW_LINE INDENT if ( spf [ j ] == 0 ) : NEW_LINE INDENT spf [ j ] = i ; NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def factorize ( n , s ) : NEW_LINE INDENT while ( n > 1 ) : NEW_LINE INDENT z = spf [ n ] ; NEW_LINE s . add ( z ) ; NEW_LINE while ( n % z == 0 ) : NEW_LINE INDENT n //= z ; NEW_LINE DEDENT DEDENT DEDENT id = [ 0 for i in range ( 100005 ) ] NEW_LINE par = [ 0 for i in range ( 100005 ) ] NEW_LINE sizeContainer = [ 0 for i in range ( 100005 ) ] NEW_LINE def root ( i ) : NEW_LINE INDENT if ( par [ i ] == i ) : NEW_LINE INDENT return i ; NEW_LINE DEDENT else : NEW_LINE INDENT return root ( par [ i ] ) ; NEW_LINE return par [ i ] NEW_LINE DEDENT DEDENT def merge ( a , b ) : NEW_LINE INDENT p = root ( a ) ; NEW_LINE q = root ( b ) ; NEW_LINE if ( p == q ) : NEW_LINE INDENT return ; NEW_LINE DEDENT if ( sizeContainer [ p ] > sizeContainer [ q ] ) : NEW_LINE INDENT p = p + q ; NEW_LINE q = p - q ; NEW_LINE p = p - q ; NEW_LINE DEDENT par [ p ] = q ; NEW_LINE sizeContainer [ q ] += sizeContainer [ p ] ; NEW_LINE DEDENT def maximumComponentsizeContainer ( a , n ) : NEW_LINE INDENT for i in range ( 100005 ) : NEW_LINE INDENT par [ i ] = i ; NEW_LINE sizeContainer [ i ] = 1 ; NEW_LINE DEDENT sieve ( ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT s = set ( ) NEW_LINE factorize ( a [ i ] , s ) ; NEW_LINE for it in s : NEW_LINE INDENT if ( id [ it ] == 0 ) : NEW_LINE INDENT id [ it ] = i + 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT merge ( i + 1 , id [ it ] ) ; NEW_LINE DEDENT DEDENT DEDENT answer = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT answer = max ( answer , sizeContainer [ i ] ) ; NEW_LINE DEDENT return answer ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 8 ; NEW_LINE A = [ 2 , 3 , 6 , 7 , 4 , 12 , 21 , 39 ] NEW_LINE print ( maximumComponentsizeContainer ( A , n ) ) ; NEW_LINE DEDENT