前言
经过前期的基础训练以及部分实战练习，粗略掌握了各种题型的解题思路。现阶段开始专项练习。
描述
给你两个正整数
left和right，请你找到两个整数num1和num2，它们满足：
left <= nums1 < nums2 <= right。nums1和nums2都是 质数 。nums2 - nums1是满足上述条件的质数对中的 最小值 。请你返回正整数数组
ans = [nums1, nums2]。如果有多个整数对满足上述条件，请你返回nums1最小的质数对。如果不存在符合题意的质数对，请你返回[-1, -1]。如果一个整数大于
1，且只能被1和它自己整除，那么它是一个 质数。示例 1：
输入：left = 10, right = 19 输出：[11,13] 解释：10 到 19 之间的质数为 11 ，13 ，17 和 19 。 质数对的最小差值是 2 ，[11,13] 和 [17,19] 都可以得到最小差值。 由于 11 比 17 小，我们返回第一个质数对。示例 2：
输入：left = 4, right = 6 输出：[-1,-1] 解释：给定范围内只有一个质数，所以题目条件无法被满足。提示：
1 <= left <= right <= 106
实现原理与步骤
1.适用埃筛法(埃拉托斯特尼筛法)查找区间内的所有素数。
2.贪心算法计算距离最小的两个素数。
实现代码
class Solution {
public int[] closestPrimes(int left, int right) {
int[] primes = getPrimesInRange(left, right);
if (primes.length < 2) {
return new int[]{-1,-1}; // 如果范围内质数少于两个
}
int minDiff = Integer.MAX_VALUE;
int[] closestPair = new int[2];
for (int i = 0; i < primes.length - 1; i++) {
int diff = primes[i + 1] - primes[i];
if (diff < minDiff) {
minDiff = diff;
closestPair[0] = primes[i];
closestPair[1] = primes[i + 1];
}
}
return closestPair;
}
public static int[] getPrimesInRange(int a, int b) {
boolean[] isPrime = new boolean[b + 1];
for (int i = 2; i <= b; i++) {
isPrime[i] = true;
}
for (int i = 2; i * i <= b; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= b; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = a; i <= b; i++) {
if (isPrime[i]) {
count++;
}
}
int[] primes = new int[count];
int index = 0;
for (int i = a; i <= b; i++) {
if (isPrime[i]) {
primes[index++] = i;
}
}
return primes;
}
}