text: Insert minimum number in array so that sum of array becomes prime | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100005 NEW_LINE bool isPrime [ MAX ] ; void sieveOfEratostheneses ( ) { memset ( isPrime , true , sizeof ( isPrime ) ) ; isPrime [ 1 ] = false ; for ( int i = 2 ; i * i < MAX ; i ++ ) { if ( isPrime [ i ] ) { for ( int j = 2 * i ; j < MAX ; j += i ) isPrime [ j ] = false ; } } } int findPrime ( int n ) { int num = n + 1 ; while ( num ) { if ( isPrime [ num ] ) return num ; num = num + 1 ; } return 0 ; } 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 ; } int main ( ) { int arr [ ] = { 2 , 4 , 6 , 8 , 12 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << minNumber ( arr , n ) ; return 0 ; }