Is Minimum Number of Primes to Sum to Target easy or hard?

The problem is generally classified as Medium difficulty. The challenge is recognizing that it behaves like the unbounded coin change problem but with primes as the available values. Once that connection is made, the dynamic programming transition becomes straightforward.

Minimum Number of Primes to Sum to Target Python/Java solution

Implementations typically start with a sieve to build the list of primes up to the target. Then a dynamic programming array updates dp[i] = min(dp[i], dp[i - p] + 1) for each prime p. The same logic translates cleanly across Python, Java, C++, Go, and TypeScript.

How to solve Minimum Number of Primes to Sum to Target in O(n)?

A strict O(n) solution generally is not achievable because multiple primes must be evaluated for every intermediate sum. The standard optimized approach uses a sieve to generate primes and dynamic programming to compute the minimum counts. This results in roughly O(n^2 / log n) time while keeping space complexity linear.

What is the best approach for Minimum Number of Primes to Sum to Target?

The most effective method combines prime preprocessing with dynamic programming. First generate all primes up to the target using the Sieve of Eratosthenes, then apply a coin-change style DP where dp[i] stores the minimum number of primes required to form sum i. This approach avoids exponential search and runs in roughly O(n^2 / log n) time with O(n) space.

Is Minimum Number of Primes to Sum to Target asked at Google/Amazon/Meta?

Problems combining primes with dynamic programming appear frequently in interviews at large tech companies. Variants of coin change, prime decomposition, and number theory DP problems have been reported in interviews at companies like Google and Amazon because they test algorithm design and preprocessing techniques.

What data structure is used in Minimum Number of Primes to Sum to Target?

The core data structure is a one-dimensional dynamic programming array where dp[i] stores the minimum number of primes needed to reach sum i. A boolean array is also commonly used during the Sieve of Eratosthenes to mark prime numbers during preprocessing.

What is the time complexity of Minimum Number of Primes to Sum to Target?

The optimal solution runs in about O(n^2 / log n) time. The sieve step takes O(n log log n) to generate primes, and the dynamic programming step iterates through each prime and updates states up to the target. Space complexity is O(n) for the DP array.

Description Hints 3 Solution Video 4:41

3610. Minimum Number of Primes to Sum to Target

Medium59.8% acceptance1 companyPremium elsewhere, free here

You are given two integers n and m.

You have to select a multiset of prime numbers 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

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Can we use dynamic programming?

Hint 2

Generate the first m prime numbers.

Hint 3

Let dp[i] represent the minimum number of prime numbers that sum up to i. Use the generated prime numbers for the transition.

4:41

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

10
2

Input

15
5

Input

7
6

Your code is saved on this device.Solution