2523. Closest Prime Numbers in Range

题目 #

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

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

Return the positive integer array ans = [nums1, nums2]. If there are multiple pairs satisfying these conditions, return the one with the minimum nums1 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$

思路1 查找质数+状态机 #

分析 #

  • 自己想的，从left到right，每个数都试试是不是质数，是质数就放到状态机计算
  • 因为时间复杂度太高，优化了一下，因为质数最小差是2和3之间差1，后面基本最小都是相差2，那么找到相差小于等于2就可以直接返回了，后面不可能比此数更小了

代码 # 

 1func isPrime(num int) bool {
 2	if num <= 1 {
 3		return false
 4	}
 5	target := int(math.Sqrt(float64(num))) + 1
 6	for i := 2; i < target; i++ {
 7		if num%i == 0 {
 8			return false
 9		}
10	}
11	return true
12}
13
14func closestPrimes(left int, right int) []int {
15	state := 0
16	p, n := 0, 0
17	result := []int{-1, -1}
18	min := math.MaxInt
19	for i := left; i <= right; i++ {
20		if !isPrime(i) {
21			continue
22		}
23		switch state {
24		case 0:
25			// 未找到第一个质数
26			state = 1
27			p = i
28		case 1:
29			// 找到第一个质数，未找到第二个
30			state = 2
31			n = i
32			result[0], result[1] = p, n
33			min = n - p
34		case 2:
35			// 两个都找到了，找个最小的
36			p, n = n, i
37			if min > n-p {
38				result[0], result[1] = p, n
39				min = n - p
40			}
41		}
42		if min <= 2 {
43			return result
44		}
45	}
46	return result
47}

思路2 欧拉线性筛+状态机 #

分析 #

  • 第一的想法，不过没我快
  • 先使用欧拉线性筛先提前筛出来 $10^6$ 以内所有的质数，然后再使用上面的状态机进行选择

代码 # 

 1var primes []int = make([]int, 0, 78500)
 2
 3func oulerPrimes(mx int, primes *[]int) {
 4	flag := make([]bool, mx+1) // 标记数有没有被筛掉，false就是没有
 5	for i := 2; i < mx+1; i++ {
 6		if !flag[i] {
 7			// 数没有被比自己小的数筛掉，就代表是质数
 8			*primes = append(*primes, i)
 9		}
10		for _, v := range *primes {
11			if i*v > mx {
12				break
13			}
14			// 每一个数都作为因子乘以比自己小的素数筛掉后面的数
15			flag[i*v] = true
16			if i%v == 0 {
17				// 减少时间复杂度的关键算法
18				// 12 = 2 * 3 * 2，i = 4时，只排了8就退出了，因为6会将12排除
19				// 也就是，假设v可以整除i即i = kv，有某个数为x = mi = kmv
20				//        那么存在一个数 i < km < x可以把x排掉，用i乘以所有的质数去排除就没什么意义了，提前退出减少时间复杂度
21				break
22			}
23		}
24	}
25}
26
27func init() {
28	oulerPrimes(1e6, &primes)
29	primes = append(primes, 1e6+1) // 加一个边界防止越界
30}
31
32func closestPrimes1(left int, right int) []int {
33	i := sort.SearchInts(primes, left)
34	state := 0
35	p, n := 0, 0
36	result := []int{-1, -1}
37	min := math.MaxInt
38	for ; primes[i] <= right; i++ {
39		switch state {
40		case 0:
41			// 未找到第一个质数
42			state = 1
43			p = primes[i]
44		case 1:
45			// 找到第一个质数，未找到第二个
46			state = 2
47			n = primes[i]
48			result[0], result[1] = p, n
49			min = n - p
50		case 2:
51			// 两个都找到了，找个最小的
52			p, n = n, primes[i]
53			if min > n-p {
54				result[0], result[1] = p, n
55				min = n - p
56			}
57		}
58	}
59	return result
60}