2614.对角线上的质数

链接：2614.对角线上的质数
难度：Easy
标签：数组、数学、矩阵、数论
简介：给你一个下标从 0 开始的二维整数数组 nums 。返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数，返回 0 。

题解 1 - cpp

• 编辑时间：2023-04-09
• 执行用时：268ms
• 内存消耗：69.8MB
• 编程语言：cpp
• 解法介绍：线性筛。

class Solution {
public:
    int diagonalPrime(vector<vector<int>>& nums) {
        int n = nums.size(), res = 0, MAX = 0;
        unordered_set<int> s;
        for (int i = 0; i < n; i++) {
            s.insert(nums[i][i]);
            s.insert(nums[i][n - 1 - i]);
            MAX = max(MAX, nums[i][i]);
            MAX = max(MAX, nums[i][n - 1 - i]);
        }
        MAX++;
        vector<int> primes(MAX, 0);
        for (int i = 2; i < MAX; i++) {
            if (primes[i] == 0) {
                primes[++primes[0]] = i;
                if (s.count(i)) res = max(res, i);
            }
            for (int j = 1; j <= primes[0] && i * primes[j] < MAX; j++) {
                primes[i * primes[j]] = 1;
                if (i % primes[j] == 0) break;
            }
        }
        return res;
    }
};

题解 2 - cpp

• 编辑时间：2023-04-09
• 执行用时：72ms
• 内存消耗：34.7MB
• 编程语言：cpp
• 解法介绍：枚举。

class Solution {
public:
    bool check(int num) {
        if (num == 1) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
    int diagonalPrime(vector<vector<int>>& nums) {
        int n = nums.size(), res = 0;
        for (int i = 0; i < n; i++) {
            if (check(nums[i][i])) res = max(res, nums[i][i]);
            if (check(nums[i][n - 1 - i])) res = max(res, nums[i][n - 1 - i]);
        }
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-04-09
• 执行用时：216ms
• 内存消耗：26.9MB
• 编程语言：python
• 解法介绍：同上。

def check(num: int):
    if num == 1:
        return False
    i = 2
    while i * i <= num:
        if num % i == 0:
            return False
        i += 1
    return True
class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        n = len(nums)
        res = 0
        for i in range(n):
            if check(nums[i][i]):
                res = max(res, nums[i][i])
            if check(nums[i][n - 1 - i]):
                res = max(res, nums[i][n - 1 - i])
        return res

题解 4 - rust

• 编辑时间：2023-04-09
• 执行用时：16ms
• 内存消耗：3.6MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn diagonal_prime(nums: Vec<Vec<i32>>) -> i32 {
        use std::cmp::max;
        let check = |num: i32| {
            if num == 1 {
                false
            } else {
                let mut i = 2;
                while i * i <= num {
                    if num % i == 0 {
                        return false;
                    }
                    i += 1;
                }
                true
            }
        };
        let n = nums.len();
        let mut res = 0;
        for i in 0..n {
            if check(nums[i][i]) {
                res = max(res, nums[i][i]);
            }
            if check(nums[i][n - 1 - i]) {
                res = max(res, nums[i][n - 1 - i]);
            }
        }
        res
    }
}