题目描述
leetcode 困难题
给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足：
left <= nums1 < nums2 <= right 。
nums1 和 nums2 都是 质数 。
nums2 - nums1 是满足上述条件的质数对中的 最小值 。
请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件，请你返回 nums1 最小的质数对。如果不存在符合题意的质数对，请你返回 [-1, -1] 。
如果一个整数大于 1 ，且只能被 1 和它自己整除，那么它是一个质数。
示例1：
1
2
3
4
5
| 输入：left = 10, right = 19
输出：[11,13]
解释：10 到 19 之间的质数为 11 ，13 ，17 和 19 。
质数对的最小差值是 2 ，[11,13] 和 [17,19] 都可以得到最小差值。
由于 11 比 17 小，我们返回第一个质数对。
|
提示1：
1
| 1 <= left <= right <= 106
|
埃氏筛
参考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
static boolean[] isPrime = new boolean[1000001];
static{
for(int i = 2; i < isPrime.length; i++){
isPrime[i] = true;
}
for(int i = 2; i * i < isPrime.length; i++){
if(!isPrime[i]){
continue;
}
for(long j = 1L * i * i; j < isPrime.length; j += i){
isPrime[(int)j] = false;
}
}
}
public int[] closestPrimes(int left, int right) {
int[] ans = {-1, -1};
int pre = -1;
for(int i = left; i <= right; i++){
if(!isPrime[i]){
continue;
}
if(pre == -1){
pre = i;
continue;
}
if(ans[0] == -1){
ans[0] = pre;
ans[1] = i;
pre = i;
continue;
}
if(i - pre < ans[1] - ans[0]){
ans[0] = pre;
ans[1] = i;
}
pre = i;
}
return ans;
}
}
|
线性筛（欧拉筛）
参考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
static int[] prime = new int[1000001];
static boolean[] visit = new boolean[1000001];
static int cnt = 0;
static{
for(int i = 2; i < visit.length; i++){
if(!visit[i]){
prime[cnt++] = i;
}
for(int j = 0; j < cnt; j++){
if(1l * i * prime[j] >= visit.length){
break;
}
visit[i * prime[j]] = true;
if(i % prime[j] == 0){
break;
}
}
}
cnt--;
}
public int[] closestPrimes(int left, int right) {
int p = -1, q = - 1;
for(int i = leftBound(left); i < cnt; i++){
if(prime[i + 1] > right){
break;
}
if(p == -1 || prime[i + 1] - prime[i] < q - p){
p = prime[i];
q = prime[i + 1];
}
}
return new int[]{p, q};
}
private int leftBound(int target){
int left = 0, right = cnt + 1;
while(left < right){
int mid = left + (right - left >> 1);
if(prime[mid] < target){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
}
|