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

```
#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;
}
```