Minimum Number of Primes to Sum to Target - Solution & Explanation

Problem Overview: You are given a target integer and need to determine the minimum number of prime numbers whose sum equals that target. Each prime can be used multiple times, and the goal is to minimize the count of primes used to reach the exact sum.

Approach 1: Brute Force Enumeration (Exponential Time, O(2^n) time, O(n) space)

The most direct idea is to try every combination of prime numbers that could sum to the target. First generate all primes up to the target using a simple primality test. Then recursively explore combinations where you add a prime and reduce the remaining target. Track the minimum number of primes used whenever the remaining value reaches zero. This approach behaves like exhaustive search and quickly becomes infeasible as the target grows because the recursion tree expands exponentially. It is useful conceptually because it reveals that the problem behaves like an unbounded combination problem similar to coin change.

Approach 2: Preprocessing + Dynamic Programming (O(n^2 / log n) time, O(n) space)

A practical solution treats each prime as a "coin" and the target as the amount to construct. Start by generating all prime numbers up to the target using the Sieve of Eratosthenes, a classic technique from number theory. This preprocessing step runs in roughly O(n log log n) time and produces the list of usable primes.

Next apply a bottom‑up dynamic programming strategy similar to the unbounded coin change problem. Create an array dp[i] representing the minimum number of primes required to form sum i. Initialize dp[0] = 0 and all other values to infinity. For every prime p, iterate through sums from p to the target and update dp[i] = min(dp[i], dp[i - p] + 1). Each update represents using prime p as the last element in the sum.

This method systematically builds answers for all smaller sums before computing the final target. The DP array ensures each state is computed once, turning the exponential brute force search into a polynomial-time solution. The algorithm mainly performs array updates and prime iterations, making it efficient even for relatively large targets. The logic relies heavily on patterns from dynamic programming and simple iteration over an array state table.

Recommended for interviews: The sieve + dynamic programming approach is what interviewers expect. Explaining the brute force recursion first demonstrates that you understand the combinational nature of the problem. Converting it into a coin-change style DP with precomputed primes shows the optimization step that interviewers look for. It also clearly communicates your understanding of state transitions and preprocessing techniques.