Generate an N | Python3 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
sieve = [ 1 ] * ( 1000000 + 1 ) NEW_LINE def sieveOfPrimes ( ) : NEW_LINE INDENT global sieve NEW_LINE N = 1000000 NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT if i * i > N : NEW_LINE INDENT break NEW_LINE DEDENT if ( sieve [ i ] == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT for j in range ( i * i , N + 1 , i ) : NEW_LINE INDENT sieve [ j ] = 0 NEW_LINE DEDENT DEDENT DEDENT def getArray ( arr , N ) : NEW_LINE INDENT global sieve NEW_LINE A = [ 0 ] * N NEW_LINE v = [ ] NEW_LINE sieveOfPrimes ( ) NEW_LINE for i in range ( 2 , int ( 1e5 ) + 1 ) : NEW_LINE INDENT if ( sieve [ i ] ) : NEW_LINE INDENT v . append ( i ) NEW_LINE DEDENT DEDENT j = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT ind = arr [ i ] NEW_LINE if ( A [ i ] != 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT elif ( A [ ind ] != 0 ) : NEW_LINE INDENT A [ i ] = A [ ind ] NEW_LINE DEDENT else : NEW_LINE INDENT prime = v [ j ] NEW_LINE A [ i ] = prime NEW_LINE A [ ind ] = A [ i ] NEW_LINE j += 1 NEW_LINE DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT print ( A [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 4 , 1 , 2 , 3 , 4 ] NEW_LINE N = len ( arr ) NEW_LINE getArray ( arr , N ) NEW_LINE DEDENT