Insert minimum number in array so that sum of array becomes prime | Java program to find minimum number to insert in array so their sum is prime ; Array to store primes ; 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
class GFG { static int MAX = 100005 ; static boolean [ ] isPrime = new boolean [ MAX ] ; static void sieveOfEratostheneses ( ) { isPrime [ 1 ] = true ; for ( int i = 2 ; i * i < MAX ; i ++ ) { if ( ! isPrime [ i ] ) { for ( int j = 2 * i ; j < MAX ; j += i ) isPrime [ j ] = true ; } } } static int findPrime ( int n ) { int num = n + 1 ; while ( num > 0 ) { if ( ! isPrime [ num ] ) return num ; num = num + 1 ; } return 0 ; } static int minNumber ( int arr [ ] , int n ) { sieveOfEratostheneses ( ) ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; if ( ! isPrime [ sum ] ) return 0 ; int num = findPrime ( sum ) ; return num - sum ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 4 , 6 , 8 , 12 } ; int n = arr . length ; System . out . println ( minNumber ( arr , n ) ) ; } }