Generate an N | Java program for the above approach ; Function to generate all prime numbers upto 10 ^ 6 ; Initialize sieve [ ] as 1 ; Iterate over the range [ 2 , N ] ; If current element is non - prime ; Make all multiples of i as 0 ; Function to construct an array A [ ] satisfying the given conditions ; Stores the resultant array ; Stores all prime numbers ; Sieve of Erastosthenes ; Append the integer i if it is a prime ; Indicates current position in list of prime numbers ; Traverse the array arr [ ] ; If already filled with another prime number ; If A [ i ] is not filled but A [ ind ] is filled ; Store A [ i ] = A [ ind ] ; If none of them were filled ; To make sure A [ i ] does not affect other values , store next prime number ; Print the resultant array ; Driver Code ; Function Call
import java . util . * ; class GFG { static int [ ] sieve = new int [ 10000000 ] ; static void sieveOfPrimes ( ) { Arrays . fill ( sieve , 1 ) ; int N = 1000000 ; for ( int i = 2 ; i * i <= N ; i ++ ) { if ( sieve [ i ] == 0 ) continue ; for ( int j = i * i ; j <= N ; j += i ) sieve [ j ] = 0 ; } } static void getArray ( int [ ] arr , int N ) { int A [ ] = new int [ N ] ; Arrays . fill ( A , 0 ) ; ArrayList < Integer > v = new ArrayList < Integer > ( ) ; sieveOfPrimes ( ) ; for ( int i = 2 ; i <= 1000000 ; i ++ ) if ( sieve [ i ] != 0 ) v . add ( i ) ; int j = 0 ; for ( int i = 0 ; i < N ; i ++ ) { int ind = arr [ i ] ; if ( A [ i ] != 0 ) continue ; else if ( A [ ind ] != 0 ) A [ i ] = A [ ind ] ; else { int prime = v . get ( j ++ ) ; A [ i ] = prime ; A [ ind ] = A [ i ] ; } } for ( int i = 0 ; i < N ; i ++ ) { System . out . print ( A [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 4 , 1 , 2 , 3 , 4 } ; int N = arr . length ; getArray ( arr , N ) ; } }