Prime in diagonal

Array Math Matrix Number Theory

37.4% acceptance

Feb 25, 2026

406

You are given a 0-indexed two-dimensional integer array nums. Return the largest prime number that lies on at least one of the diagonals of nums. In case, no prime is present on any of the diagonals, return 0. Note that: An integer is prime if it is greater than 1 and has no positive integer divisors other than 1 and itself. An integer val is on one of the diagonals of nums if there exists an integer i for which nums[i][i] = val or an i for which nums[i][nums.length - i - 1] = val.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn diagonal_prime(nums: Vec<Vec<i32>>) -> i32 {
    let n = nums.len();

    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 = 3i32;
      while i * i <= x {
        if x % i == 0 { return false; }
        i += 2;
      }
      true
    }

    let mut ans = 0;
    for i in 0..n {
      let v1 = nums[i][i];
      let v2 = nums[i][n - 1 - i];
      if is_prime(v1) && v1 > ans { ans = v1; }
      if is_prime(v2) && v2 > ans { ans = v2; }
    }
    ans
  }
}