Nearest prime number in the array of every array element | Java 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 code
import java . util . * ; class GFG { static final int max = 10000000 ; static boolean [ ] prime = new boolean [ max ] ; static 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 ; } } } } static void print_nearest_prime ( int arr [ ] , int N ) { int maxm = Arrays . stream ( arr ) . max ( ) . getAsInt ( ) ; SieveOfEratosthenes ( maxm ) ; Vector < Integer > primes = new Vector < Integer > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( ! prime [ arr [ i ] ] ) primes . add ( i ) ; } if ( primes . size ( ) == 0 ) { for ( int i = 0 ; i < N ; i ++ ) { System . out . print ( - 1 + " ▁ " ) ; } return ; } int curr = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( curr == primes . size ( ) - 1 || i <= primes . get ( curr ) ) { System . out . print ( arr [ primes . get ( curr ) ] + " ▁ " ) ; continue ; } if ( Math . abs ( primes . get ( curr ) - i ) < Math . abs ( primes . get ( curr + 1 ) - i ) ) { System . out . print ( arr [ primes . get ( curr ) ] + " ▁ " ) ; } else { curr ++ ; System . out . print ( arr [ primes . get ( curr ) ] + " ▁ " ) ; } } } public static void main ( String [ ] args ) { int N = 6 ; int arr [ ] = { 8 , 7 , 12 , 15 , 3 , 11 } ; print_nearest_prime ( arr , N ) ; } }