Classic Dynamic Programming IX

A bit of vibe code together with OpenAI O3. I asked O3 to just generate the sieve due to laziness. Sieve is used to calculate the first M primes (when I was using Miller-Rabin, was giving me TLE). The DP follows from that in a straightforward way: calculate the numbers from i..n-1, then n follows by calculating the min over all M primes. Notice that I made use of Goldbach's Conjecture as a way to optimize the code too. Goldbach's Conjecture estates that any even number greater than 2 is the sum of 2 primes. The conjecture is applied in the highlighted line. Cheers, ACC.

PS: the prompt for the sieve was the following, again using Open AI O3 Advanced Reasoning: "give me a sieve to find the first M prime numbers in C#. The code should produce a List<int> with the first M primes"

Minimum Number of Primes to Sum to Target - LeetCode

You are given two integers n and m.

You have to select a multiset of  from the first m prime numbers such that the sum of the selected primes is exactly n. You may use each prime number multiple times.

Return the minimum number of prime numbers needed to sum up to n, or -1 if it is not possible.

 

Example 1:

Input: n = 10, m = 2

Output: 4

Explanation:

The first 2 primes are [2, 3]. The sum 10 can be formed as 2 + 2 + 3 + 3, requiring 4 primes.

Example 2:

Input: n = 15, m = 5

Output: 3

Explanation:

The first 5 primes are [2, 3, 5, 7, 11]. The sum 15 can be formed as 5 + 5 + 5, requiring 3 primes.

Example 3:

Input: n = 7, m = 6

Output: 1

Explanation:

The first 6 primes are [2, 3, 5, 7, 11, 13]. The sum 7 can be formed directly by prime 7, requiring only 1 prime.

 

Constraints:

• 1 <= n <= 1000
• 1 <= m <= 1000

---

Seen this question in a real interview before?

1/5

Yes

No

Accepted

117/149

Acceptance Rate

78.5%

public class Solution {
    public List FirstPrimes(int count)
    {
        if (count <= 0) return new List();

        // Small cases outright
        if (count == 1) return new List { 2 };

        // Prime-number-theorem upper-bound estimate for the n-th prime:
        //  p_n < n (log n + log log n)  for n ≥ 6.
        int EstimateUpperBound(int n)
        {
            if (n < 6) return 15;                    // covers up to the 5th prime (11)
            double nn = n;
            double bound = nn * (Math.Log(nn) + Math.Log(Math.Log(nn)));
            return (int)bound + 3;                   // safety margin
        }

        int limit = EstimateUpperBound(count);

        while (true)
        {
            // Sieve boolean array: true = composite; false = prime (tentative)
            bool[] isComposite = new bool[limit + 1];

            // Sieve core
            for (int p = 2; p * p <= limit; ++p)
            {
                if (!isComposite[p])
                {
                    for (int mult = p * p; mult <= limit; mult += p)
                        isComposite[mult] = true;
                }
            }

            // Collect primes
            var primes = new List(count);
            for (int i = 2; i <= limit && primes.Count < count; ++i)
            {
                if (!isComposite[i]) primes.Add(i);
            }

            if (primes.Count == count)
                return primes;                       // done

            // If we arrive here, the estimate was too low → enlarge and repeat
            limit = limit * 2;                       // geometric growth is sufficient
        }
    }

    public int MinNumberOfPrimes(int n, int m)
    {
        List primes = FirstPrimes(m);

        if (primes.Contains(n)) return 1;
        if (m >= n && n % 2 == 0) return 2;

        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++)
        {
            if (primes.Contains(i))
            {
                dp[i] = 1;
            }
            else
            {
                foreach (int prime in primes)
                {
                    if (i - prime < 0) break;
                    if (dp[i - prime] > 0)
                    {
                        if (dp[i] == 0) dp[i] = dp[i - prime] + 1;
                        else dp[i] = Math.Min(dp[i], dp[i - prime] + 1);
                    }
                }
            }
        }

        return dp[n] == 0 ? -1 : dp[n];
    }
}