2523. 范围内最接近的两个质数

🟠 🔖 数学 数论 🔗 力扣open in new window LeetCodeopen in new window

题目

Given two positive integers left and right, find the two integers num1 and num2 such that:

left <= num1 < num2 <= right .
num1 and num2 are both prime numbers.
num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the minimumnum1 value or [-1, -1] if such numbers do not exist.

A number greater than 1 is called prime if it is only divisible by 1 and itself.

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints:

1 <= left <= right <= 10^6

题目大意

给你两个正整数 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 <= 10^6

解题思路

1. 使用埃拉托色尼筛法

埃拉托色尼筛法是一种高效找出 1 到 n 之间所有质数的方法，时间复杂度为 O(n log log n)，比朴素的 O(n√n) 质数判断快得多。

对于范围 [2, n]：

先假设所有数都是质数。
从 2 开始，将 2 的所有倍数（4, 6, 8, ...）标记为合数（非质数）。
找到下一个未被标记的数 p（它仍然是质数），再标记 p 的所有倍数为合数。
重复步骤 2-3，直到 p^2 > n，筛选结束。
最后，所有未被标记的数就是质数。

2. 遍历 [left, right] 找最近质数对

记录上一个质数 prev，计算当前质数 curr 之间的间距。
维护最小间距的质数对。

复杂度分析

时间复杂度：O(n log log n)
- 埃氏筛预处理：O(n log log n)
- 遍历范围 [left, right] 查找：O(n)
空间复杂度：O(n)，存储质数标记。

代码

/**
 * @param {number} left
 * @param {number} right
 * @return {number[]}
 */
var closestPrimes = function (left, right) {
	// 埃氏筛预处理所有质数
	const sieve = new Array(right + 1).fill(true);
	sieve[0] = sieve[1] = false; // 0 和 1 不是质数
	for (let i = 2; i * i <= right; i++) {
		if (sieve[i]) {
			for (let j = i * i; j <= right; j += i) {
				sieve[j] = false;
			}
		}
	}

	// 遍历 [left, right]，找最近的质数对
	let prev = -1,
		minGap = Infinity,
		result = [-1, -1];
	for (let i = left; i <= right; i++) {
		if (sieve[i]) {
			if (prev !== -1 && i - prev < minGap) {
				minGap = i - prev;
				result = [prev, i];
			}
			prev = i;
		}
	}

	return result;
};

2523. 范围内最接近的两个质数

# 2523. 范围内最接近的两个质数

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

2523. 范围内最接近的两个质数

题目

题目大意

解题思路

复杂度分析

代码

相关题目