跳转至

3610. Minimum Number of Primes to Sum to Target 🔒

题目描述

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

解法

方法一：预处理 + 动态规划

我们可以先预处理得到前 \(1000\) 个素数，然后使用动态规划来求解。

定义 \(f[i]\) 为和为 \(i\) 的最小素数个数，初始时 \(f[0] = 0\)，其他 \(f[i] = \infty\)。对于每个素数 \(p\)，我们可以从 \(f[i - p]\) 更新到 \(f[i]\)，即

\[ f[i] = \min(f[i], f[i - p] + 1) \]

如果 \(f[n]\) 仍然为 \(\infty\)，则说明无法用前 \(m\) 个素数的和得到 \(n\)，返回 -1；否则返回 \(f[n]\)。

时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(n + M)\)，其中 \(M\) 为预处理的素数个数（这里为 \(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;
}

评论