1import java.util.*;
2
3// This class provides methods to work with prime numbers and compute minimum counts for sum representations.
4class Solution {
5    // Static list storing the first M prime numbers.
6    static List<Integer> primes = new ArrayList<>();
7
8    // Static initialization block to populate the prime list.
9    static {
10        int candidate = 2;       // Candidate number to check for primeness.
11        int maxPrimes = 1000;    // Number of primes to precompute.
12        while (primes.size() < maxPrimes) {
13            boolean isPrime = true;
14            for (int prime : primes) {
15                // If prime*prime > candidate, no need to check further.
16                if (prime * prime > candidate) {
17                    break;
18                }
19                // If divisible, not a prime.
20                if (candidate % prime == 0) {
21                    isPrime = false;
22                    break;
23                }
24            }
25            // If candidate is prime, add to list.
26            if (isPrime) {
27                primes.add(candidate);
28            }
29            candidate++;
30        }
31    }
32
33    /**
34     * Returns the minimum number of prime numbers (from the first m primes)
35     * that sum up to n. If it's not possible, returns -1.
36     *
37     * This is a classic unbounded knapsack problem.
38     *
39     * @param n the target sum
40     * @param m the number of allowed primes (from the start)
41     * @return minimum count of primes needed to sum to n, or -1 if impossible
42     */
43    public int minNumberOfPrimes(int n, int m) {
44        int[] dp = new int[n + 1]; // dp[i]: min number of primes to sum to i
45        final int INF = 1 << 30;   // A large number representing infinity
46        Arrays.fill(dp, INF);
47        dp[0] = 0; // Zero primes needed for sum 0
48
49        // For each of the first m primes
50        for (int prime : primes.subList(0, m)) {
51            // For each sum >= prime
52            for (int sum = prime; sum <= n; sum++) {
53                // Unbounded knapsack: you can use this prime multiple times.
54                dp[s
55um] = Math.min(dp[sum], dp[sum - prime] + 1);
56            }
57        }
58        // If a valid answer was found, return it. Otherwise, return -1.
59        return dp[n] < INF ? dp[n] : -1;
60    }
61}
62

1class Solution {
2public:
3    int minNumberOfPrimes(int n, int m) {
4        // Static vector to cache the smallest 1000 prime numbers
5        static std::vector<int> primes;
6
7        // Initialize the prime list if it's empty
8        if (primes.empty()) {
9            int candidate = 2;
10            int targetPrimeCount = 1000;
11            while ((int)primes.size() < targetPrimeCount) {
12                bool isPrime = true;
13                // Check divisibility by previously found primes (up to sqrt(candidate))
14                for (int prime : primes) {
15                    if (prime * prime > candidate) break;
16                    if (candidate % prime == 0) {
17                        isPrime = false;
18                        break;
19                    }
20                }
21                if (isPrime) primes.push_back(candidate);
22                ++candidate;
23            }
24        }
25
26        // DP approach: f[i] = minimum number of primes needed to sum up to i
27        std::vector<int> f(n + 1, INT_MAX);
28        f[0] = 0; // Base case
29
30        // Use the first 'm' primes for the solution
31        for (int prime : std::vector<int>(primes.begin(), primes.begin() + m)) {
32            for (int sum = prime; sum <= n; ++sum) {
33                if (f[sum - prime] != INT_MAX) {
34                    f[sum] = std::min(f[sum], f[sum - prime] + 1);
35                }
36            }
37        }
38
39        // If a solution exists, return the minimum number of primes, else return -1
40        return f[n] < INT_MAX ? f[n] : -1;
41    }
42};
43

1// Generate the first 1000 prime numbers and store them in the 'primes' array
2const primes: number[] = [];
3let x = 2;              // Current number to check for primality
4const M = 1000;         // Number of primes to generate
5
6while (primes.length < M) {
7    let isPrime = true;
8    // Check if `x` is divisible by any previously found primes <= sqrt(x)
9    for (const prime of primes) {
10        if (prime * prime > x) break;
11        if (x % prime === 0) {
12            isPrime = false;
13            break;
14        }
15    }
16    if (isPrime) {
17        primes.push(x);
18    }
19    x++;
20}
21
22/**
23 * Computes the minimum number of primes (selected from the first `m` primes)
24 * that sum up to `n`. Returns -1 if no such combination exists.
25 *
26 * @param n - Target sum
27 * @param m - Number of first primes to use
28 * @returns Minimum number of primes needed, or -1 if impossible
29 */
30function minNumberOfPrimes(n: number, m: number): number {
31    const INF = 1e9;       // Represent infinity (unreachable state)
32    const dp: number[] = Array(n + 1).fill(INF);  // dp[i]: min number of primes to sum to i
33    dp[0] = 0;             // Base case: 0 can be formed by 0 primes
34
35    // Only use the first `m` primes
36    for (const prime of primes.slice(0, m)) {
37        // Classic unbounded knapsack dynamic programming loop
38        for (let i = prime; i <= n; i++) {
39            if (dp[i - prime] < INF) {
40                dp[i] = Math.min(dp[i], dp[i - prime] + 1);
41            }
42        }
43    }
44
45    // If not possible return -1, otherwise return the minimum count found
46    return dp[n] < INF ? dp[n] : -1;
47}
48