Largest prime from consecutive prime sum

Array Math Number Theory

38.9% acceptance

Feb 25, 2026

You are given an integer n. Return the largest prime number less than or equal to n that can be expressed as the sum of one or more consecutive prime numbers starting from 2. If no such number exists, return 0.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn largest_prime(n: i32) -> i32 {
    fn is_prime(x: i32) -> bool {
      if x < 2 { return false; }
      if x == 2 { return true; }
      if x % 2 == 0 { return false; }
      let mut i = 3;
      while i * i <= x { if x % i == 0 { return false; } i += 2; }
      true
    }
    let mut sum = 0i32;
    let mut ans = 0i32;
    let mut p = 2i32;
    loop {
      if p > n { break; }
      if !is_prime(p) { p += 1; continue; }
      sum += p;
      if sum > n { break; }
      if is_prime(sum) { ans = sum; }
      p += 1;
    }
    ans
  }
}