Nearest element with at | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 100001 ; const int INF = INT_MAX ; int primedivisor [ MAX ] , dist [ MAX ] , pos [ MAX ] , divInd [ MAX ] ; vector < int > divisors [ MAX ] ; void sieveOfEratosthenes ( ) { for ( int i = 2 ; i * i < MAX ; ++ i ) { if ( ! primedivisor [ i ] ) for ( int j = i * i ; j < MAX ; j += i ) primedivisor [ j ] = i ; } for ( int i = 1 ; i < MAX ; ++ i ) if ( ! primedivisor [ i ] ) primedivisor [ i ] = i ; } 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 [ i ] . push_back ( div ) ; while ( num % div == 0 ) num /= div ; } } } void nearestGCD ( int arr [ ] , int n ) { findDivisors ( arr , n ) ; for ( int i = 0 ; i < n ; ++ i ) { for ( auto & div : divisors [ i ] ) { if ( divInd [ div ] == -1 ) divInd [ div ] = i ; else { int ind = divInd [ div ] ; divInd [ div ] = i ; if ( dist [ i ] > abs ( ind - i ) ) { dist [ i ] = abs ( ind - i ) ; pos [ i ] = ind + 1 ; } if ( dist [ ind ] > abs ( ind - i ) ) { dist [ ind ] = abs ( ind - i ) ; pos [ ind ] = i + 1 ; } } } } } int main ( ) { sieveOfEratosthenes ( ) ; int arr [ ] = { 2 , 9 , 4 , 3 , 13 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; nearestGCD ( arr , n ) ; for ( int i = 0 ; i < n ; ++ i ) cout << pos [ i ] << " ▁ " ; return 0 ; }