Largest Divisor for each element in an array other than 1 and the number itself | Python3 implementation of the approach ; Divisors array to keep track of the maximum divisor ; Function to pre - compute the prime numbers and largest divisors ; Visited array to keep track of prime numbers ; 0 and 1 are not prime numbers ; Initialising divisors [ i ] = i ; For all the numbers divisible by 2 the maximum divisor will be number / 2 ; If divisors [ i ] is not equal to i then this means that divisors [ i ] contains minimum prime divisor for the number ; Update the answer to i / smallest_prime_divisor [ i ] ; Condition if i is a prime number ; If divisors [ j ] is equal to j then this means that i is the first prime divisor for j so we update divi [ j ] = i ; If the current element is prime then it has no divisors other than 1 and itself ; Driver code
maxin = 100001 ; NEW_LINE divisors = [ 0 ] * ( maxin + 1 ) ; NEW_LINE def Calc_Max_Div ( arr , n ) : NEW_LINE INDENT vis = [ 1 ] * ( maxin + 1 ) ; NEW_LINE vis [ 0 ] = vis [ 1 ] = 0 ; NEW_LINE for i in range ( 1 , maxin + 1 ) : NEW_LINE INDENT divisors [ i ] = i ; NEW_LINE DEDENT for i in range ( 4 , maxin + 1 , 2 ) : NEW_LINE INDENT vis [ i ] = 0 ; NEW_LINE divisors [ i ] = i // 2 ; NEW_LINE DEDENT for i in range ( 3 , maxin + 1 , 2 ) : NEW_LINE INDENT if ( divisors [ i ] != i ) : NEW_LINE INDENT divisors [ i ] = i // divisors [ i ] ; NEW_LINE DEDENT if ( vis [ i ] == 1 ) : NEW_LINE INDENT for j in range ( i * i , maxin , i ) : NEW_LINE INDENT vis [ j ] = 0 ; NEW_LINE if ( divisors [ j ] == j ) : NEW_LINE INDENT divisors [ j ] = i ; NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ( divisors [ arr [ i ] ] == arr [ i ] ) : NEW_LINE INDENT print ( " - 1 ▁ " , end = " " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( divisors [ arr [ i ] ] , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 6 , 7 , 8 , 9 , 10 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE Calc_Max_Div ( arr , n ) ; NEW_LINE DEDENT