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 <= 10001 <= m <= 1000We can first preprocess to obtain the first 1000 prime numbers, and then use dynamic programming to solve the problem.
Define f[i] as the minimum number of primes needed to sum up to i. Initially, set f[0] = 0 and all other f[i] = infty. For each prime p, we can update f[i] from f[i - p] as follows:
$
f[i] = min(f[i], f[i - p] + 1)
If f[n] is still infty, it means it is impossible to obtain n as the sum of the first m primes, so return -1; otherwise, return f[n].
The time complexity is O(m times n), and the space complexity is O(n + M), where M is the number of preprocessed primes (here it is 1000$).
Java
C++
Go
TypeScript
Practice Minimum Number of Primes to Sum to Target with our built-in code editor and test cases.
Practice on FleetCode