【LetMeFly】2614.對角線上的質數：遍歷(質數判斷)

力扣題目鏈接：https://leetcode.cn/problems/prime-in-diagonal/

給你一個下標從 0 開始的二維整數數組 nums 。

返回位于 nums 至少一條 對角線 上的最大 質數 。如果任一對角線上均不存在質數，返回 0 。

注意：

• 如果某個整數大于 1 ，且不存在除 1 和自身之外的正整數因子，則認為該整數是一個質數。
• 如果存在整數 i ，使得?nums[i][i] = val 或者?nums[i][nums.length - i - 1]= val ，則認為整數 val 位于 nums 的一條對角線上。

在上圖中，一條對角線是 [1,5,9] ，而另一條對角線是 [3,5,7] 。

?

示例 1：

輸入：nums = [[1,2,3],[5,6,7],[9,10,11]]
輸出：11
解釋：數字 1、3、6、9 和 11 是所有 "位于至少一條對角線上" 的數字。由于 11 是最大的質數，故返回 11 。

示例 2：

輸入：nums = [[1,2,3],[5,17,7],[9,11,10]]
輸出：17
解釋：數字 1、3、9、10 和 17 是所有滿足"位于至少一條對角線上"的數字。由于 17 是最大的質數，故返回 17 。

?

提示：

• 1 <= nums.length <= 300
• nums.length == numsi.length
• 1 <= nums[i][j]?<= 4*106

解題方法：質數判斷

如何判斷一個數是否為質數？

首先如果這個數小于2那么一定不是質數

用$i$從2到$sqrt(n)$枚舉，若$i$能整除$n$，則$n$不是質數

否則$n$是質數

如何遍歷對角線？題目中說了 nums.length == numsi.length ，也就是說矩陣是正方形。

所以我們可以用$i$從$0$枚舉到$n?1$，那么$nums[i][i]$和$nums[i][len(nums)?i?1]$即為對角線和副對角線上的元素。

• 時間復雜度$O(len(nums)\sqrt{\max (nums[i][j]))}$
• 空間復雜度$O(1)$

AC代碼

C++

/** @Author: LetMeFly* @Date: 2025-03-18 23:40:09* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-18 23:43:36*/
class Solution {
private:bool isPrime(int n) {if (n < 2) {return false;}int k = sqrt(n);for (int i = 2; i <= k; i++) {if (n % i == 0) {return false;}}return true;}
public:int diagonalPrime(vector<vector<int>>& nums) {int ans = 0;for (int i = 0; i < nums.size(); i++) {if (isPrime(nums[i][i])) {ans = max(ans, nums[i][i]);}if (isPrime(nums[i][nums.size() - i - 1])) {ans = max(ans, nums[i][nums.size() - i - 1]);}}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-03-18 23:46:52
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-18 23:48:14
'''
from typing import List
from math import sqrtclass Solution:def isPrime(self, n: int) -> bool:if n < 2:return Falsefor i in range(2, int(sqrt(n)) + 1):if n % i == 0:return Falsereturn Truedef diagonalPrime(self, nums: List[List[int]]) -> int:ans = 0for i in range(len(nums)):if self.isPrime(nums[i][i]):ans = max(ans, nums[i][i])if self.isPrime(nums[i][len(nums) - i - 1]):ans = max(ans, nums[i][len(nums) - i - 1])return ans

Java

/** @Author: LetMeFly* @Date: 2025-03-18 23:50:23* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-18 23:55:24*/
class Solution {private boolean isPrime(int n) {if (n < 2) {return false;}int k = (int)Math.sqrt(n);for (int i = 2; i <= k; i++) {if (n % i == 0) {return false;}}return true;}public int diagonalPrime(int[][] nums) {int ans = 0;for (int i = 0; i < nums.length; i++) {if (isPrime(nums[i][i])) {ans = Math.max(ans, nums[i][i]);}if (isPrime(nums[i][nums.length - i - 1])) {ans = Math.max(ans, nums[i][nums.length - i - 1]);}}return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-03-18 23:55:55* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-18 23:58:46*/
package mainfunc isPrime2614(n int) (ans bool) {if n < 2 {return}for i := 2; i * i <= n; i++ {if n % i == 0 {return}}return true
}func diagonalPrime(nums [][]int) (ans int) {for i := range nums {if isPrime2614(nums[i][i]) {ans = max(ans, nums[i][i])}if isPrime2614(nums[i][len(nums) - i - 1]) {ans = max(ans, nums[i][len(nums) - i - 1])}}return
}

同步發文于CSDN和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

千篇源碼題解已開源