Nearest element with at | Python3 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 ; 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
MAX = 100001 NEW_LINE INF = 10 ** 9 NEW_LINE primedivisor = [ 0 for i in range ( MAX ) ] NEW_LINE dist = [ 0 for i in range ( MAX ) ] NEW_LINE pos = [ 0 for i in range ( MAX ) ] NEW_LINE divInd = [ 0 for i in range ( MAX ) ] NEW_LINE divisors = [ [ ] for i in range ( MAX ) ] NEW_LINE def sieveOfEratosthenes ( ) : NEW_LINE INDENT for i in range ( 2 , MAX ) : NEW_LINE INDENT if i * i > MAX : NEW_LINE INDENT break NEW_LINE DEDENT if ( primedivisor [ i ] == 0 ) : NEW_LINE INDENT for j in range ( 2 * i , MAX , i ) : NEW_LINE INDENT primedivisor [ j ] = i NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , MAX ) : NEW_LINE INDENT if ( primedivisor [ i ] == 0 ) : NEW_LINE INDENT primedivisor [ i ] = i NEW_LINE DEDENT DEDENT DEDENT def findDivisors ( arr , n ) : NEW_LINE INDENT for i in range ( MAX ) : NEW_LINE INDENT pos [ i ] = divInd [ i ] = - 1 NEW_LINE dist [ i ] = 10 ** 9 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT num = arr [ i ] NEW_LINE while ( num > 1 ) : NEW_LINE INDENT div = primedivisor [ num ] NEW_LINE divisors [ i ] . append ( div ) NEW_LINE while ( num % div == 0 ) : NEW_LINE INDENT num //= div NEW_LINE DEDENT DEDENT DEDENT DEDENT def nearestGCD ( arr , n ) : NEW_LINE INDENT findDivisors ( arr , n ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT for div in divisors [ i ] : NEW_LINE INDENT if ( divInd [ div ] == - 1 ) : NEW_LINE INDENT divInd [ div ] = i NEW_LINE DEDENT else : NEW_LINE INDENT ind = divInd [ div ] NEW_LINE divInd [ div ] = i NEW_LINE if ( dist [ i ] > abs ( ind - i ) ) : NEW_LINE INDENT dist [ i ] = abs ( ind - i ) NEW_LINE pos [ i ] = ind + 1 NEW_LINE DEDENT if ( dist [ ind ] > abs ( ind - i ) ) : NEW_LINE DEDENT DEDENT DEDENT DEDENT ' NEW_LINE INDENT dist [ ind ] = abs ( ind - i ) NEW_LINE pos [ ind ] = i + 1 NEW_LINE DEDENT sieveOfEratosthenes ( ) NEW_LINE arr = [ 2 , 9 , 4 , 3 , 13 ] NEW_LINE n = len ( arr ) NEW_LINE nearestGCD ( arr , n ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( pos [ i ] , end = " ▁ " ) NEW_LINE DEDENT