Largest Divisor for each element in an array other than 1 and the number itself | Javascript 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
var maxin = 100001 ; var divisors = Array ( maxin ) . fill ( 0 ) ; function Calc_Max_Div ( arr , n ) { var vis = Array ( maxin ) . fill ( 1 ) ; vis [ 0 ] = vis [ 1 ] = 0 ; var i , j ; for ( i = 1 ; i <= maxin ; i ++ ) divisors [ i ] = i ; for ( i = 4 ; i <= maxin ; i += 2 ) { vis [ i ] = 0 ; divisors [ i ] = i / 2 ; } for ( i = 3 ; i <= maxin ; i += 2 ) { if ( divisors [ i ] != i ) { divisors [ i ] = i / divisors [ i ] ; } if ( vis [ i ] == 1 ) { for ( j = i * i ; j < maxin ; j += i ) { vis [ j ] = 0 ; if ( divisors [ j ] == j ) divisors [ j ] = i ; } } } for ( i = 0 ; i < n ; i ++ ) { if ( divisors [ arr [ i ] ] == arr [ i ] ) document . write ( " " ) ; else document . write ( divisors [ arr [ i ] ] + " " ) ; } } var arr = [ 5 , 6 , 7 , 8 , 9 , 10 ] ; var n = arr . length ; Calc_Max_Div ( arr , n ) ;