Insert minimum number in array so that sum of array becomes prime | Python3 program to find minimum number to insert in array so their sum is prime ; function to calculate prime using sieve of eratosthenes ; Find prime number greater than a number ; find prime greater than n ; check if num is prime ; Increment num ; To find number to be added so sum of array is prime ; call sieveOfEratostheneses to calculate primes ; To find sum of array elements ; If sum is already prime return 0 ; To find prime number greater than sum ; Return difference of sum and num ; Driver code
isPrime = [ 1 ] * 100005 NEW_LINE def sieveOfEratostheneses ( ) : NEW_LINE INDENT isPrime [ 1 ] = False NEW_LINE i = 2 NEW_LINE while i * i < 100005 : NEW_LINE INDENT if ( isPrime [ i ] ) : NEW_LINE INDENT j = 2 * i NEW_LINE while j < 100005 : NEW_LINE INDENT isPrime [ j ] = False NEW_LINE j += i NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT return NEW_LINE DEDENT def findPrime ( n ) : NEW_LINE INDENT num = n + 1 NEW_LINE while ( num ) : NEW_LINE INDENT if isPrime [ num ] : NEW_LINE INDENT return num NEW_LINE DEDENT num += 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT def minNumber ( arr ) : NEW_LINE INDENT sieveOfEratostheneses ( ) NEW_LINE s = 0 NEW_LINE for i in range ( 0 , len ( arr ) ) : NEW_LINE INDENT s += arr [ i ] NEW_LINE DEDENT if isPrime [ s ] == True : NEW_LINE INDENT return 0 NEW_LINE DEDENT num = findPrime ( s ) NEW_LINE return num - s NEW_LINE DEDENT arr = [ 2 , 4 , 6 , 8 , 12 ] NEW_LINE print ( minNumber ( arr ) ) NEW_LINE