Minimum changes required to make all Array elements Prime | Function to generate all primes ; If p is a prime ; Mark all its multiples as non - prime ; Store all prime numbers ; Return the list of primes ; Function to calculate the minimum increments to convert every array elements to a prime ; Extract maximum element of the given array ; Extract the index which has the next greater prime ; Store the difference between the prime and the array element ; Driver code
def SieveOfEratosthenes ( n ) : NEW_LINE INDENT prime = [ True for i in range ( 2 * n + 1 ) ] NEW_LINE p = 2 NEW_LINE while ( p * p <= 2 * n ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT i = p * p NEW_LINE while ( i <= n * 2 ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE i += p NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT primes = [ ] NEW_LINE for p in range ( 2 , ( 2 * n ) + 1 ) : NEW_LINE INDENT if ( prime [ p ] ) : NEW_LINE INDENT primes . append ( p ) NEW_LINE DEDENT DEDENT return primes NEW_LINE DEDENT def minChanges ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE ans = 0 NEW_LINE maxi = max ( arr ) NEW_LINE primes = SieveOfEratosthenes ( maxi ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT x = - 1 NEW_LINE for j in range ( len ( primes ) ) : NEW_LINE INDENT if ( arr [ i ] == primes [ j ] ) : NEW_LINE INDENT x = j NEW_LINE break NEW_LINE DEDENT elif ( arr [ i ] < primes [ j ] ) : NEW_LINE INDENT x = j NEW_LINE break NEW_LINE DEDENT DEDENT minm = abs ( primes [ x ] - arr [ i ] ) NEW_LINE if ( x > 1 ) : NEW_LINE INDENT minm = min ( minm , abs ( primes [ x - 1 ] - arr [ i ] ) ) NEW_LINE DEDENT ans += minm NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 4 , 25 , 13 , 6 , 20 ] NEW_LINE print ( minChanges ( arr ) ) NEW_LINE