Nearest prime number in the array of every array element | C ++ program to find nearest prime number in the array for all array elements ; Create a boolean array and set all entries it as false . A value in prime [ i ] will be true if i is not a prime , else false ; Sieve of Eratosthenes function ; Update all multiples of i greater than or equal to the square of it numbers which are multiple of i and are less than i ^ 2 are already been marked . ; Function to find nearest prime number for all elements ; Compute and store all prime numbers up to maxm ; Store the indices of all primes ; If no primes are present in the array ; Store the current prime ; If the no further primes exist in the array ; For all indices less than that of the current prime ; If the current prime is nearer ; If the next prime is nearer ; Make the next prime as the current ; Driver Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define max  10000000 NEW_LINE bool prime [ max ] = { false } ; void SieveOfEratosthenes ( int maxm ) { prime [ 0 ] = prime [ 1 ] = true ; for ( int i = 2 ; i * i <= maxm ; i ++ ) { if ( ! prime [ i ] ) { for ( int j = i * i ; j <= maxm ; j += i ) { prime [ j ] = true ; } } } } void print_nearest_prime ( int arr [ ] , int N ) { int maxm = * max_element ( arr , arr + N ) ; SieveOfEratosthenes ( maxm ) ; vector < int > primes ; for ( int i = 0 ; i < N ; i ++ ) { if ( ! prime [ arr [ i ] ] ) primes . push_back ( i ) ; } if ( primes . size ( ) == 0 ) { for ( int i = 0 ; i < N ; i ++ ) { cout << -1 << " ▁ " ; } return ; } int curr = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( curr == primes . size ( ) - 1 || i <= primes [ curr ] ) { cout << arr [ primes [ curr ] ] << " ▁ " ; continue ; } if ( abs ( primes [ curr ] - i ) < abs ( primes [ curr + 1 ] - i ) ) { cout << arr [ primes [ curr ] ] << " ▁ " ; } else { curr ++ ; cout << arr [ primes [ curr ] ] << " ▁ " ; } } } int main ( ) { int N = 6 ; int arr [ ] = { 8 , 7 , 12 , 15 , 3 , 11 } ; print_nearest_prime ( arr , N ) ; return 0 ; }