Nearest element with at | Javascript program to print nearest element with at least one common prime factor . ; Pre - computation of smallest prime divisor of all numbers ; Prime number will have same divisor ; Function to calculate all divisors of input array ; Pre - compute all the divisors of array element by using prime factors ; Traverse all elements , ; For every divisor of current element , find closest element . ; Visit divisor if not visited ; Fetch the index of visited divisor ; Update the divisor index to current index ; Set the minimum distance ; Set the min distance of current index ' i ' to nearest one ; Add 1 as indexing starts from 0 ; Set the min distance of found index ' ind ' ; Add 1 as indexing starts from 0 ; Driver code ; Simple sieve to find smallest prime divisor of number from 2 to MAX ; function to calculate nearest distance of every array elements ; Print the nearest distance having GDC > 1
let MAX = 100001 ; let INF = Number . MAX_VALUE ; let primedivisor = new Array ( MAX ) ; let dist = new Array ( MAX ) ; let pos = new Array ( MAX ) ; let divInd = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { primedivisor [ i ] = 0 ; dist [ i ] = 0 ; pos [ i ] = 0 ; divInd [ i ] = 0 ; } let divisors = [ ] ; function sieveOfEratosthenes ( ) { for ( let i = 2 ; i * i < MAX ; ++ i ) { if ( primedivisor [ i ] == 0 ) { for ( let j = i * i ; j < MAX ; j += i ) { primedivisor [ j ] = i ; } } } for ( let i = 1 ; i < MAX ; ++ i ) { if ( primedivisor [ i ] == 0 ) { primedivisor [ i ] = i ; } } } function findDivisors ( arr , n ) { for ( let i = 0 ; i < MAX ; ++ i ) { pos [ i ] = divInd [ i ] = - 1 ; dist [ i ] = INF ; } for ( let i = 0 ; i < n ; ++ i ) { let num = arr [ i ] ; while ( num > 1 ) { let div = primedivisor [ num ] ; divisors [ i ] . push ( div ) ; while ( num % div == 0 ) { num = Math . floor ( num / div ) ; } } } } function nearestGCD ( arr , n ) { findDivisors ( arr , n ) ; for ( let i = 0 ; i < n ; ++ i ) { for ( let div = 0 ; div < divisors [ i ] . length ; div ++ ) { if ( divInd [ divisors [ i ] [ div ] ] == - 1 ) { divInd [ divisors [ i ] [ div ] ] = i ; } else { let ind = divInd [ divisors [ i ] [ div ] ] ; divInd [ divisors [ i ] [ div ] ] = i ; if ( dist [ i ] > Math . abs ( ind - i ) ) { dist [ i ] = Math . abs ( ind - i ) ; pos [ i ] = ind + 1 ; } if ( dist [ ind ] > Math . abs ( ind - i ) ) { dist [ ind ] = Math . abs ( ind - i ) ; pos [ ind ] = i + 1 ; } } } } } for ( let i = 0 ; i < MAX ; i ++ ) { divisors . push ( [ ] ) ; } sieveOfEratosthenes ( ) ; let arr = [ 2 , 9 , 4 , 3 , 13 ] ; let n = arr . length ; nearestGCD ( arr , n ) ; for ( let i = 0 ; i < n ; ++ i ) { document . write ( pos [ i ] + " " ) ; }