Minimum number of primes to sum to target

Array Math Dynamic Programming Number Theory

59.8% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_number_of_primes(n: i32, m: i32) -> i32 {
    let mut primes = Vec::new();
    let mut candidate = 2;
    while primes.len() < m as usize {
      if Self::is_prime(candidate) {
        primes.push(candidate as usize);
      }
      candidate += 1;
    }
    let n = n as usize;
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;
    for i in 1..=n {
      for &p in &primes {
        if p > i { break; }
        if dp[i - p] != i32::MAX {
          dp[i] = dp[i].min(dp[i - p] + 1);
        }
      }
    }
    if dp[n] == i32::MAX { -1 } else { dp[n] }
  }

  fn is_prime(n: i32) -> bool {
    if n < 2 { return false; }
    if n < 4 { return true; }
    if n % 2 == 0 || n % 3 == 0 { return false; }
    let mut i = 5;
    while i * i <= n {
      if n % i == 0 || n % (i + 2) == 0 { return false; }
      i += 6;
    }
    true
  }
}