Insert minimum number in array so that sum of array becomes prime | PHP program to find minimum number to insert in array so their sum is prime ; function to calculate primes using sieve of eratosthenes ; Find prime number greater than a number ; To return prime number 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 ; To find prime number greater then sum ; Return difference of sum and num ; Driver Code
< ? php $ MAX = 100005 ; function sieveOfEratostheneses ( ) { $ isPrime = array_fill ( true , $ MAX , NULL ) ; $ isPrime [ 1 ] = false ; for ( $ i = 2 ; $ i * $ i < $ MAX ; $ i ++ ) { if ( $ isPrime [ $ i ] ) { for ( $ j = 2 * $ i ; $ j < $ MAX ; $ j += $ i ) $ isPrime [ $ j ] = false ; } } } function findPrime ( $ n ) { $ num = $ n + 1 ; while ( $ num ) { if ( $ isPrime [ $ num ] ) return $ num ; $ num = $ num + 1 ; } return 0 ; } function minNumber ( & $ arr , $ n ) { sieveOfEratostheneses ( ) ; $ sum = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ sum += $ arr [ $ i ] ; if ( $ isPrime [ $ sum ] ) return 0 ; $ num = findPrime ( $ sum ) ; return $ num - $ sum ; } $ arr = array ( 2 , 4 , 6 , 8 , 12 ) ; $ n = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; echo minNumber ( $ arr , $ n ) ; return 0 ; ? >