本文涉及知识点

数论：质数、最大公约数、菲蜀定理

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

给你两个正整数 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⁶

质数筛选

通过欧拉筛或埃氏筛获取所以小于等于right的质数，存放到向量v中，显然v是升序。
二分查找 * it >= left的最小it。
二分查找 * ij > right的最小ij。
if(ij -it<2) 返回{-1,-1}。
对应的下标分别为i1,i2。
i2–
for(;i1<i2; i1++)
(v[i1+1]-v[i1])便是差值

代码

class CUniqueFactorization
{
public:
	CUniqueFactorization(int iMax) {
		int iMaxSqrt = sqrt(iMax) + 2;
		m_vPrime = CreatePrime(iMaxSqrt);
	}
	void Factorization(int x) {
		m_a.clear();
		m_n.clear();
		for (const auto& iPre : m_vPrime) {
			int cnt = 0;
			while (0 == x % iPre) {
				cnt++;
				x /= iPre;
			}
			if (cnt > 0) {
				m_a.emplace_back(iPre);
				m_n.emplace_back(cnt);
			}
		}
		if (x > 1) {
			m_a.emplace_back(x);
			m_n.emplace_back(1);
		}
	}
	vector<int> m_a, m_n;
	vector<int> CreatePrimeOld(int iMax)
	{
		vector<int> vNo(iMax + 1);
		vector<int> vPrime;
		for (int i = 2; i <= iMax; i++)
		{
			if (!vNo[i])
			{
				vPrime.emplace_back(i);
			}
			for (const auto& n : vPrime)
			{
				if (n * i > iMax)
				{
					break;
				}
				vNo[n * i] = true;
			}
		}
		return vPrime;
	}
	static vector<int> CreatePrime(int iMax)
	{
		vector<bool> isPrime(iMax + 1, true);
		vector<int> vPrime;
		for (int i = 2; i <= iMax; i++)
		{
			if (isPrime[i])
			{
				vPrime.emplace_back(i);
			}
			for (const auto& n : vPrime)
			{
				if (n * i > iMax) { break; }
				isPrime[n * i] = false;
				if (0 == i % n) { break; }
			}
		}
		return vPrime;
	}
	vector<int> m_vPrime;
};

		class Solution {
		public:
			vector<int> closestPrimes(int left, int right) {
				auto v = CUniqueFactorization::CreatePrime(right);
				auto i1 = lower_bound(v.begin(), v.end(), left) - v.begin();
				auto i2 = upper_bound(v.begin(), v.end(), right) - v.begin();
				vector<int> ans = { -1,-1 };
				i2--;
				int iMin = INT_MAX;
				for (; i1 < i2; i1++) {
					if (v[i1 + 1] - v[i1] < iMin) {
						iMin = v[i1 + 1] - v[i1];
						ans = { v[i1] ,v[i1 + 1] };
					}
				}
				return ans;
			}
		};

单元测试

TEST_METHOD(TestMethod11)
		{
			auto res = Solution().closestPrimes(10,19);
			AssertEx({ 11,13 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().closestPrimes(4, 6);
			AssertEx({ -1,-1 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			auto res = Solution().closestPrimes(8, 10);
			AssertEx({ -1,-1 }, res);
		}