Minimum prime numbers required to be subtracted to make all array elements equal | Python3 program for the above approach ; Stores the sieve of prime numbers ; Function that performs the Sieve of Eratosthenes ; Iterate over the range [ 2 , 1000 ] ; If the current element is a prime number ; Mark all its multiples as false ; Function to find the minimum number of subtraction of primes numbers required to make all array elements the same ; Perform sieve of eratosthenes ; Find the minimum value ; Stores the value to each array element should be reduced ; If an element exists with value ( M + 1 ) ; Stores the minimum count of subtraction of prime numbers ; Traverse the array ; If D is equal to 0 ; If D is a prime number ; Increase count by 1 ; If D is an even number ; Increase count by 2 ; If D - 2 is prime ; Increase count by 2 ; Otherwise , increase count by 3 ; Driver Code
import sys NEW_LINE limit = 100000 NEW_LINE prime = [ True ] * ( limit + 1 ) NEW_LINE def sieve ( ) : NEW_LINE INDENT p = 2 NEW_LINE while ( p * p <= limit ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , limit , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def findOperations ( arr , n ) : NEW_LINE INDENT sieve ( ) NEW_LINE minm = sys . maxsize NEW_LINE for i in range ( n ) : NEW_LINE INDENT minm = min ( minm , arr [ i ] ) NEW_LINE DEDENT val = minm NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] == minm + 1 ) : NEW_LINE INDENT val = minm - 2 NEW_LINE break NEW_LINE DEDENT DEDENT cnt = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT D = arr [ i ] - val NEW_LINE if ( D == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT elif ( prime [ D ] == True ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT elif ( D % 2 == 0 ) : NEW_LINE INDENT cnt += 2 NEW_LINE DEDENT else : NEW_LINE INDENT if ( prime [ D - 2 ] == True ) : NEW_LINE INDENT cnt += 2 NEW_LINE DEDENT else : NEW_LINE INDENT cnt += 3 NEW_LINE DEDENT DEDENT DEDENT return cnt NEW_LINE DEDENT arr = [ 7 , 10 , 4 , 5 ] NEW_LINE N = 4 NEW_LINE print ( findOperations ( arr , N ) ) NEW_LINE