Minimum changes required to make all Array elements Prime | C ++ Program to implement the above approach ; Function to generate all primes ; If p is a prime ; Mark all its multiples as non - prime ; Store all prime numbers ; Return the list of primes ; Function to calculate the minimum increments to convert every array elements to a prime ; Extract maximum element of the given array ; Extract the index which has the next greater prime ; Store the difference between the prime and the array element ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > SieveOfEratosthenes ( int n ) { bool prime [ 2 * n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; for ( int p = 2 ; p * p <= 2 * n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= 2 * n ; i += p ) prime [ i ] = false ; } } vector < int > primes ; for ( int p = 2 ; p <= 2 * n ; p ++ ) if ( prime [ p ] ) primes . push_back ( p ) ; return primes ; } int minChanges ( vector < int > arr ) { int n = arr . size ( ) ; int ans = 0 ; int maxi = * max_element ( arr . begin ( ) , arr . end ( ) ) ; vector < int > primes = SieveOfEratosthenes ( maxi ) ; for ( int i = 0 ; i < n ; i ++ ) { int x = lower_bound ( primes . begin ( ) , primes . end ( ) , arr [ i ] ) - primes . begin ( ) ; int minm = abs ( primes [ x ] - arr [ i ] ) ; if ( x > 1 ) { minm = min ( minm , abs ( primes [ x - 1 ] - arr [ i ] ) ) ; } ans += minm ; } return ans ; } int main ( ) { vector < int > arr = { 4 , 25 , 13 , 6 , 20 } ; cout << minChanges ( arr ) ; return 0 ; }