3115、质数的最大距离

leetcode 数组数学数论

Created At : 2024-07-02 21:00

Count:283 Views 👀 :

Comment:

示例 1：
示例 2：

分析

二次根号内取余判断

给你一个整数数组 nums。

返回两个（不一定不同的）质数在 nums 中下标的最大距离。

示例 1：

输入： nums = [4,2,9,5,3]

输出： 3

解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

示例 2：

输入： nums = [4,8,2,8]

输出： 0

解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。

提示：

$1 <= nums.length <= 3 * 10^5$
$1 <= nums[i] <= 100$
输入保证 nums 中至少有一个质数。

分析

判断质数的方法：

筛法
缓存判断法
逐个取余法

二次根号内取余判断


class Solution {
    public int maximumPrimeDifference(int[] nums) {
        int n = nums.length;
        int start = -1;
        int end = -1;
        for(int i = 0;i < n;i++) {
            if (isPrime(nums[i])) {
                start = i;
                break;
            }
        }

        for(int i = n - 1;i >= 0;i--) {
            if (isPrime(nums[i])) {
                end = i;
                break;
            }
        }
        // System.out.println("end = " + end + ",start = " + start);
        return end - start;
    }

    public boolean isPrime(int num) {
        if (num == 1) {
            return false;
        }
        if (num == 2 || num == 3) {
            return true;
        }
        for (int i = 2;i <= Math.sqrt(num);i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com