2614 对角线上的质数

· 2025-3-18   · 次阅读   · 字数统计: 164字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

2614. 对角线上的质数

分析

遍历判断即可，由于数据范围较小，直接判断快过质数筛

代码实现

class Solution {
public:
    int diagonalPrime(vector<vector<int>>& nums) {
        int ans = 0, n = nums.size();
        auto checkPrime = [](int x) {
            for(int i = 2; i * i <= x; ++i) {
                if(x % i == 0)
                    return false;
            }
            return x == 1 ? false : true;
        };


        for(int i = 0; i < n; ++i) {
            if(nums[i][i] > ans && checkPrime(nums[i][i]))
                ans = nums[i][i];
    
            if(nums[i][n - i - 1] > ans && checkPrime(nums[i][n - i - 1]))
                ans = nums[i][n - i - 1];
        }

        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n \sqrt{ans})$
  • 空间复杂度：$O(1)$