Minimum primes less than 1000 required to produce sum N

You are given an integer N.You have to use minimum no. of primes less than 1000 that sum equals to N. If it is not possible to produce a sum, print -1. Otherwise, output minimum primes required.
for example:
N=6
output:
2
explaination: 3+3=6
N=7666
output:
8

Note: This question was asked in yesterday’s interview bit academy test.

2 Likes

Learn about Dp coin change.

2 Likes

You need to generate prime numbers till 1000.
Then treat this prime numbers has coins with value equal to that prime number.
Preform “Coin change with minimum coins” problem logic on these prime value coins ans number N.

1 Like

suppose there is no constraint on which prime we can use.
Then if N is even:

         if N is  2 then answer is 1 (since 2 itself is prime)
         if N is not 2  then answer is 2 (because as per Goldbach's conjecture any even > 2 can be expressed as  sum of two primes.)

if N is odd :

          if N is prime answer is 1
        else  if  (N-2) is prime answer is 2
         else answer is 3 ( Because (N-anyprime) =even which can be expressed as sum of two   primes so (N-p1)=p2+p3 : N=p1+p2+p3)

NOW we have given constraint that we have to use primes less than 1000:
997 is largest prime less than 1000 so we have , so to minimize number of prime we have to use we 997 will come floor(N/997) time now N becomes N= Nmod 997 now minimum primes required can be obtained by above algo .

TO sum up Let F(N ) be the function which gives Minimum primes less than 1000 required to produce sum N and G(N) gives Minimum primes required to produce sum N

F(N)=floor(N/997)+G(N mod 997)

Well, this problem is a mix of two basic concepts.
1.) sieve of eratosthenes.(for finding primes till 1000)
2.) DP- coin change problem.(for finding minimum primes to make n)

You literally have to combine them. thats it!

So, You could easily search both of them online and understand them.
I tried to code the problem. Please check if it’s correct :stuck_out_tongue:

#include <bits/stdc++.h>

using namespace std;
#define fastio			std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test int t;cin>>t;while(t--)


vector<int> prime;

void precomp_prime() // Sieve of EraTHANOS  O(x*log(log(x))) x is till where you want the primes
{
bool isprime[1001];
memset(isprime,true,sizeof(isprime));

for(int i=2;i*i<1001;i++)
{
	if(isprime[i]==true)
	{
		for(int j=i*i;j<1001;j+=i)
			isprime[j]=false;
	}
}

for(int i=2;i<1001;i++)
{
	if(isprime[i])
		prime.push_back(i);
}
}

int minCoins(vector<int> coins, int m, int V) // dp=coin change O(mV)
{ 

int table[V+1]; 

table[0] = 0; 

for (int i=1; i<=V; i++) 
    table[i] = INT_MAX; 

 for (int i=1; i<=V; i++) 
{ 
   for (int j=0; j<m; j++) 
      if (coins[j] <= i) 
      { 
          int sub_res = table[i-coins[j]]; 
          if (sub_res != INT_MAX && sub_res + 1 < table[i]) 
              table[i] = sub_res + 1; 
      } 
} 
return table[V]; 
} 

int main() {
#ifndef ONLINE_JUDGE
	freopen("inp.txt", "r", stdin);
	freopen("output.txt","w", stdout);
#endif
fastio;

precomp_prime();

test{

	/*for(int i=0;i<prime.size();i++)
		cout<<prime[i]<<" ";*/
	int n;cin>>n;

	cout<<minCoins(prime,prime.size(),n)<<"\n";

}


return 0;
}