Question Name:PRIME NUMBERS AGAIN

#include <iostream>
using namespace std;
int main()
{

int avi,b,i;
  cin>>avi;
  for(i=0;i<avi;i++) { 
    cin>>b;
    if(b==1) 
    { 
      cout<<0<<endl; 
    } 
    if( b==3 || b==4 || b==2 || b==5 || b==7) 
    { 
      cout<<1<<endl;
    } 
    if( b==6||b==9||b==8||b==10||b==21)
    { 
      cout<<2<<endl;
    } 
  } 
    
 return 0;
}

Problem Description
Panda can do any problem anytime and anywhere. Panda is doing an extensive research on prime numbers. Milinda has got a question for Panda. The only way for Panda to impress Milinda is by solving this question.

Given a number N, find the minimum number of primatic numbers which sum upto N.

A primatic number refers to a number which is either a prime number or can be expressed as power of prime number to itself i.e. prime^prime e.g. 4, 27, etc.

Note: 8, 32, etc are not primatic numbers.
Panda is very sad since he is unable to solve the problem. Please help Panda in solving this problem.

Input Format:
The first line will contain two integers: T, the number of test cases.
Each test case consists of a single integer N.

Output Format:
For each query output the minimum number of primatic numbers which can sum upto N.

Constraints:
1 <= T <= 10^5
2 <= N <= 10^4

Subtask 1:
T = 100, 2 <= N <= 1000 – 20 points

Subtask 2:
T = 10^5, 2 <= N <= 104 – 80 points
Test Case 1
Input (stdin)
2
6 3
Expected Output
2
1
Test Case 2
Input (stdin)
11
4 2 1 3 5 7 6 9 8 10 21
Expected Output
1
1
0
1
1
1
2
2
2
2
2

Problem Breakdown:

Panda is interested in solving a problem related to primatic numbers. A primatic number refers to:

A prime number (like 2, 3, 5, 7).
A number that is a power of a prime number to itself (like $4 = 2^2$ , $27 = 3^3$ , $9 = 3^2$ ).

Given a number $N$ , the goal is to find the minimum number of primatic numbers that sum up to $N$ . In each test case, we need to determine this minimal combination for a given $N$ .

Input Format:

The first line contains an integer $T$ (number of test cases).
For each test case, there is a single integer $N$ .

Output Format:

For each test case, print the minimum number of primatic numbers that sum up to $N$ .

Problem Constraints:

$1 \leq T \leq 10^5$
$2 \leq N \leq 10^4$

Plan of Action:

Primatic Numbers:
- We need to first generate all prime numbers and primatic numbers less than or equal to 10,000. This can be done using the Sieve of Eratosthenes for primes and then calculating powers of primes to generate the additional primatic numbers (like $2^2 = 4$ , $3^3 = 27$ , etc.).
Dynamic Programming (DP):
- Once we have all the primatic numbers, we can use a dynamic programming approach to compute the minimum number of primatic numbers that sum up to each number from 1 to 10,000.
- The idea is similar to the coin change problem where we try to minimize the number of "coins" (primatic numbers) to sum up to a value.
Efficient Query Answering:
- Precompute the solution for every $N$ from 1 to 10,000 and then for each query, directly return the result in constant time.

Step-by-Step Approach:

Generate Primatic Numbers:
- First, use the Sieve of Eratosthenes to find all prime numbers up to 10,000.
- Then, calculate the powers of these prime numbers (like $2^2$ , $3^3$ ) to find additional primatic numbers.
Dynamic Programming Setup:
- Use a DP array where dp[i] represents the minimum number of primatic numbers that sum up to $i$ .
- Initialize dp[0] = 0 (since no numbers are needed to sum up to 0).
- For each primatic number, update the DP array using a similar approach to the coin change problem: $dp[i] = \min(dp[i], dp[i - \text{primatic number}] + 1)$
Answering Queries:
- After precomputing the DP array, for each query, simply print the result stored in dp[N].

Code Explanation:


#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_N = 10000;
vector<int> primatics; // To store all primatic numbers
int dp[MAX_N + 1];     // DP array to store the minimum number of primatic numbers

// Function to generate prime numbers using Sieve of Eratosthenes
vector<int> generate_primes(int limit) {
    vector<int> primes;
    vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

// Function to generate all primatic numbers
void generate_primatics() {
    vector<int> primes = generate_primes(MAX_N);

    // Add all primes to primatics
    for (int prime : primes) {
        primatics.push_back(prime);
    }

    // Add prime powers (prime^prime) to primatics (e.g. 4, 27, 9, etc.)
    for (int prime : primes) {
        int power = prime * prime;
        while (power <= MAX_N) {
            primatics.push_back(power);
            power *= prime;
        }
    }

    // Sort and remove duplicates if any
    sort(primatics.begin(), primatics.end());
    primatics.erase(unique(primatics.begin(), primatics.end()), primatics.end());
}

// Function to precompute the minimum number of primatic numbers for each N
void precompute_dp() {
    // Initialize dp array with a large number (infinity)
    fill(dp, dp + MAX_N + 1, MAX_N + 1);
    dp[0] = 0;

    // Fill the dp array (similar to the coin change problem)
    for (int p : primatics) {
        for (int i = p; i <= MAX_N; i++) {
            dp[i] = min(dp[i], dp[i - p] + 1);
        }
    }
}

int main() {
    // Generate all primatic numbers
    generate_primatics();

    // Precompute the minimum number of primatic numbers for each N
    precompute_dp();

    int T, N;
    cin >> T;

    // Process each test case
    while (T--) {
        cin >> N;
        cout << dp[N] << endl;
    }

    return 0;
}

Detailed Explanation:

Prime Number Generation:
- The generate_primes function uses the Sieve of Eratosthenes to find all prime numbers up to 10,000.
Primatic Number Generation:
- After generating all prime numbers, we calculate the prime powers that are less than or equal to 10,000. For example, for $2$ , we calculate $2^2 = 4$ , $2^3 = 8$ , etc., until the value exceeds 10,000.
- The primatics vector contains all prime numbers and prime powers.
Dynamic Programming Setup:
- The precompute_dp function initializes the DP array dp[] where dp[i] holds the minimum number of primatic numbers required to sum up to $i$ .
- Initially, dp[0] = 0 (since no numbers are needed to sum to zero), and all other values are set to a large number (effectively infinity).
- We iterate through each primatic number and update the DP array using the coin change dynamic programming method: $dp[i] = \min(dp[i], dp[i - \text{primatic number}] + 1)$
- This ensures that for each $i$ , we find the minimum number of primatic numbers that sum up to $i$ .
Query Processing:
- After precomputing the DP array, each test case can be answered in constant time by simply looking up the precomputed result in dp[N].

Time and Space Complexity:

Time Complexity:
- Prime and Primatic Generation: Generating primes takes $O(N \log \log N)$ , and calculating prime powers is $O(N)$ .
- Dynamic Programming: Filling the DP array is $O(N \times P)$ , where $N = 10,000$ and $P$ is the number of primatic numbers. In this case, $P$ is small (less than 100), so the complexity is manageable.
- Query Processing: Each query is answered in constant time $O(1)$ .
Space Complexity:
- The DP array requires $O(N)$ space where $N = 10,000$ .
- The primatic numbers list requires $O(P)$ space.

Example Walkthrough:

Test Case 1:

Input:

2
6
3

For $N = 6$ : The minimum primatic numbers that sum to 6 are $2 + 2 + 2$ , so the answer is 2.
For $N = 3$ : The number itself is a prime, so the answer is 1.

Output:

2
1

Test Case 2: