代码编织梦想

LeetCode第2523题-范围内最接近的两个质数-java实现-图解思路与手撕代码


一、题目描述

给你两个正整数 left 和 right ,请你找到两个整数 num1 和 num2 ,它们满足:

1、left <= nums1 < nums2 <= right 。
2、nums1 和 nums2 都是 质数 。
3、nums2 - nums1 是满足上述条件的质数对中的最小值 。

请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件,请你返回 nums1 最小的质数对。如果不存在符合题意的质数对,请你返回 [-1, -1] 。

如果一个整数大于 1 ,且只能被 1 和它自己整除,那么它是一个质数。

二、解题思路与代码实现

1.解题思路

对[left, right]范围内的所有质数进行条件筛选。

2.代码实现

代码如下(示例):

    private static int[] closestPrimes(int left, int right) {
        int[] nums = sieveOfEratosthenes(right), res = new int[]{-1, -1};
//        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= left) {
                if (res[0] == -1 || (i + 1 < nums.length && (nums[i + 1] - nums[i]) < (res[1] - res[0]))) {
                    res[0] = nums[i];
                    if (i + 1 < nums.length) {
                        res[1] = nums[i + 1];
                    }
                }
            }
        }
        if (res[1] > right || res[1] == -1) {
            return new int[]{-1, -1};
        } else {
            return res;
        }
    }

埃拉托色尼筛选法,返回小于等于n的素数

    // 埃拉托色尼筛选法,返回小于等于n的素数
    private static int[] sieveOfEratosthenes(int n) {
        boolean[] prime = new boolean[n + 1];
        int i;
        for (i = 2; i <= n; i++) {
            prime[i] = true;
        }
        for (int divisor = 2; divisor * divisor <= n; divisor++) {
            if (prime[divisor]) {
                for (i = 2 * divisor; i <= n; i = i + divisor) {
                    prime[i] = false;
                }
            }
        }
        List<Integer> res = new LinkedList<>();
        for (i = 2; i <= n; i++) {
            if (prime[i]) {
                res.add(i);
            }
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

欧拉线性筛素数,返回小于等于n的所有素数

    // 欧拉线性筛素数,返回小于等于n的所有素数
    private static int[] eulerFlagPrime(int n) {
        boolean[] flag = new boolean[n + 1];
        List<Integer> prime_numbers = new LinkedList<>();
        for (int num = 2; num < n + 1; num++) {
            if (!flag[num]) {
                prime_numbers.add(num);
            }
            for (int prime : prime_numbers) {
                if (num * prime > n) {
                    break;
                }
                flag[num * prime] = true;
                if (num % prime == 0) {
                    break;
                }
            }
        }
        return prime_numbers.stream().mapToInt(Integer::valueOf).toArray();
    }
}


总结

这道题主要是求质数,有了这两种求质数的方法,遇到其他类似题目就不用担心了。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45271005/article/details/128526420

leetcode第3题无重复字符的最长子串-java实现-图解思路与手撕代码-滑动窗口_在下柠檬的博客-爱代码爱编程

LeetCode第3题无重复字符的最长子串-java实现-图解思路与手撕代码-滑动窗口 文章目录 一、题目描述二、解题思路与代码实现1.思路2.滑动窗口的代码 总结 一、题目描述 给定一个

leetcode第9题-回文数-java实现-图解思路与手撕代码_在下柠檬的博客-爱代码爱编程

LeetCode第9题-回文数-java实现-图解思路与手撕代码 文章目录 一、题目描述二、解题思路与代码实现1.解题思路2.代码实现 总结 一、题目描述 给你一个整数 x ,如果 x 是

leetcode第29题-两数相除-java实现-图解思路与手撕代码_在下柠檬的博客-爱代码爱编程

LeetCode第29题-两数相除-java实现-图解思路与手撕代码 文章目录 一、题目描述二、解题思路与代码实现1.解题思路2.相加部分实现 总结 一、题目描述 给定两个整数,被除数 d

【二叉搜索树】-手撕加图解_芸芸众生奈我何的博客-爱代码爱编程

定义 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删

leetcode第50题-pow(x,n)-java实现-图解思路与手撕代码-爱代码爱编程

LeetCode第50题-pow(x,n)-java实现-图解思路与手撕代码 文章目录 一、题目描述二、解题思路与代码实现1.解题思路2.代码实现 总结 一、题目描述 实现 pow(x,

leetcode第45题-爱代码爱编程

LeetCode第45题-跳跃游戏||-java实现-图解思路与手撕代码 文章目录 一、题目描述二、解题思路与代码实现1.解题思路2.代码实现 总结 一、题目描述 给你一个非负