Nearest element with at | Java 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
import java . io . * ; import java . util . * ; class GFG { static int MAX = 100001 ; static int INF = Integer . MAX_VALUE ; static int [ ] primedivisor = new int [ MAX ] ; static int [ ] dist = new int [ MAX ] ; static int [ ] pos = new int [ MAX ] ; static int [ ] divInd = new int [ MAX ] ; static ArrayList < ArrayList < Integer > > divisors = new ArrayList < ArrayList < Integer > > ( ) ; static void sieveOfEratosthenes ( ) { for ( int i = 2 ; i * i < MAX ; ++ i ) { if ( primedivisor [ i ] == 0 ) { for ( int j = i * i ; j < MAX ; j += i ) { primedivisor [ j ] = i ; } } } for ( int i = 1 ; i < MAX ; ++ i ) { if ( primedivisor [ i ] == 0 ) { primedivisor [ i ] = i ; } } } static void findDivisors ( int arr [ ] , int n ) { for ( int i = 0 ; i < MAX ; ++ i ) { pos [ i ] = divInd [ i ] = - 1 ; dist [ i ] = INF ; } for ( int i = 0 ; i < n ; ++ i ) { int num = arr [ i ] ; while ( num > 1 ) { int div = primedivisor [ num ] ; divisors . get ( i ) . add ( div ) ; while ( num % div == 0 ) { num /= div ; } } } } static void nearestGCD ( int arr [ ] , int n ) { findDivisors ( arr , n ) ; for ( int i = 0 ; i < n ; ++ i ) { for ( int div : divisors . get ( i ) ) { if ( divInd [ div ] == - 1 ) { divInd [ div ] = i ; } else { int ind = divInd [ div ] ; divInd [ 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 ; } } } } } public static void main ( String [ ] args ) { for ( int i = 0 ; i < MAX ; i ++ ) { divisors . add ( new ArrayList < Integer > ( ) ) ; } sieveOfEratosthenes ( ) ; int arr [ ] = { 2 , 9 , 4 , 3 , 13 } ; int n = arr . length ; nearestGCD ( arr , n ) ; for ( int i = 0 ; i < n ; ++ i ) { System . out . print ( pos [ i ] + " ▁ " ) ; } } }