Skip to content

3610. Minimum Number of Primes to Sum to Target πŸ”’

Description

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

Solutions

Solution 1: Preprocessing + Dynamic Programming

Thinking

Forming \(n\) from the first \(m\) primes with repetition is an unbounded knapsack. Combinatorial search is unnecessary: \(n,m\le 1000\) admits an \(O(mn)\) recurrence.

Sieve the first \(1000\) primes. Let \(f[i]\) be the fewest primes that sum to \(i\), with \(f[0]=0\) and the rest \(\infty\).

For each prime \(p\), scan \(i\) upward and set \(f[i]=\min(f[i],f[i-p]+1)\) so the same prime may be reused. If \(f[n]\) stays \(\infty\), return \(-1\).

We 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\)).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
primes = []
x = 2
M = 1000
while len(primes) < M:
    is_prime = True
    for p in primes:
        if p * p > x:
            break
        if x % p == 0:
            is_prime = False
            break
    if is_prime:
        primes.append(x)
    x += 1


class Solution:
    def minNumberOfPrimes(self, n: int, m: int) -> int:
        min = lambda x, y: x if x < y else y
        f = [0] + [inf] * n
        for x in primes[:m]:
            for i in range(x, n + 1):
                f[i] = min(f[i], f[i - x] + 1)
        return f[n] if f[n] < inf else -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    static List<Integer> primes = new ArrayList<>();
    static {
        int x = 2;
        int M = 1000;
        while (primes.size() < M) {
            boolean is_prime = true;
            for (int p : primes) {
                if (p * p > x) {
                    break;
                }
                if (x % p == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                primes.add(x);
            }
            x++;
        }
    }

    public int minNumberOfPrimes(int n, int m) {
        int[] f = new int[n + 1];
        final int inf = 1 << 30;
        Arrays.fill(f, inf);
        f[0] = 0;
        for (int x : primes.subList(0, m)) {
            for (int i = x; i <= n; i++) {
                f[i] = Math.min(f[i], f[i - x] + 1);
            }
        }
        return f[n] < inf ? f[n] : -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int minNumberOfPrimes(int n, int m) {
        static vector<int> primes;
        if (primes.empty()) {
            int x = 2;
            int M = 1000;
            while ((int) primes.size() < M) {
                bool is_prime = true;
                for (int p : primes) {
                    if (p * p > x) break;
                    if (x % p == 0) {
                        is_prime = false;
                        break;
                    }
                }
                if (is_prime) primes.push_back(x);
                x++;
            }
        }

        vector<int> f(n + 1, INT_MAX);
        f[0] = 0;
        for (int x : vector<int>(primes.begin(), primes.begin() + m)) {
            for (int i = x; i <= n; ++i) {
                if (f[i - x] != INT_MAX) {
                    f[i] = min(f[i], f[i - x] + 1);
                }
            }
        }
        return f[n] < INT_MAX ? f[n] : -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
var primes []int

func init() {
    x := 2
    M := 1000
    for len(primes) < M {
        is_prime := true
        for _, p := range primes {
            if p*p > x {
                break
            }
            if x%p == 0 {
                is_prime = false
                break
            }
        }
        if is_prime {
            primes = append(primes, x)
        }
        x++
    }
}

func minNumberOfPrimes(n int, m int) int {
    const inf = int(1e9)
    f := make([]int, n+1)
    for i := 1; i <= n; i++ {
        f[i] = inf
    }
    f[0] = 0

    for _, x := range primes[:m] {
        for i := x; i <= n; i++ {
            if f[i-x] < inf && f[i-x]+1 < f[i] {
                f[i] = f[i-x] + 1
            }
        }
    }

    if f[n] < inf {
        return f[n]
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const primes: number[] = [];
let x = 2;
const M = 1000;
while (primes.length < M) {
    let is_prime = true;
    for (const p of primes) {
        if (p * p > x) break;
        if (x % p === 0) {
            is_prime = false;
            break;
        }
    }
    if (is_prime) primes.push(x);
    x++;
}

function minNumberOfPrimes(n: number, m: number): number {
    const inf = 1e9;
    const f: number[] = Array(n + 1).fill(inf);
    f[0] = 0;

    for (const x of primes.slice(0, m)) {
        for (let i = x; i <= n; i++) {
            if (f[i - x] < inf) {
                f[i] = Math.min(f[i], f[i - x] + 1);
            }
        }
    }

    return f[n] < inf ? f[n] : -1;
}

Comments