Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2523.html

2523. Closest Prime Numbers in Range

Description

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 <= 106

 

Solutions

  • class Solution {
        public int[] closestPrimes(int left, int right) {
            int cnt = 0;
            boolean[] st = new boolean[right + 1];
            int[] prime = new int[right + 1];
            for (int i = 2; i <= right; ++i) {
                if (!st[i]) {
                    prime[cnt++] = i;
                }
                for (int j = 0; prime[j] <= right / i; ++j) {
                    st[prime[j] * i] = true;
                    if (i % prime[j] == 0) {
                        break;
                    }
                }
            }
            int i = -1, j = -1;
            for (int k = 0; k < cnt; ++k) {
                if (prime[k] >= left && prime[k] <= right) {
                    if (i == -1) {
                        i = k;
                    }
                    j = k;
                }
            }
            int[] ans = new int[] {-1, -1};
            if (i == j || i == -1) {
                return ans;
            }
            int mi = 1 << 30;
            for (int k = i; k < j; ++k) {
                int d = prime[k + 1] - prime[k];
                if (d < mi) {
                    mi = d;
                    ans[0] = prime[k];
                    ans[1] = prime[k + 1];
                }
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        vector<int> closestPrimes(int left, int right) {
            int cnt = 0;
            bool st[right + 1];
            memset(st, 0, sizeof st);
            int prime[right + 1];
            for (int i = 2; i <= right; ++i) {
                if (!st[i]) {
                    prime[cnt++] = i;
                }
                for (int j = 0; prime[j] <= right / i; ++j) {
                    st[prime[j] * i] = true;
                    if (i % prime[j] == 0) {
                        break;
                    }
                }
            }
            int i = -1, j = -1;
            for (int k = 0; k < cnt; ++k) {
                if (prime[k] >= left && prime[k] <= right) {
                    if (i == -1) {
                        i = k;
                    }
                    j = k;
                }
            }
            vector<int> ans = {-1, -1};
            if (i == j || i == -1) return ans;
            int mi = 1 << 30;
            for (int k = i; k < j; ++k) {
                int d = prime[k + 1] - prime[k];
                if (d < mi) {
                    mi = d;
                    ans[0] = prime[k];
                    ans[1] = prime[k + 1];
                }
            }
            return ans;
        }
    };
    
  • class Solution:
        def closestPrimes(self, left: int, right: int) -> List[int]:
            cnt = 0
            st = [False] * (right + 1)
            prime = [0] * (right + 1)
            for i in range(2, right + 1):
                if not st[i]:
                    prime[cnt] = i
                    cnt += 1
                j = 0
                while prime[j] <= right // i:
                    st[prime[j] * i] = 1
                    if i % prime[j] == 0:
                        break
                    j += 1
            p = [v for v in prime[:cnt] if left <= v <= right]
            mi = inf
            ans = [-1, -1]
            for a, b in pairwise(p):
                if (d := b - a) < mi:
                    mi = d
                    ans = [a, b]
            return ans
    
    
  • func closestPrimes(left int, right int) []int {
    	cnt := 0
    	st := make([]bool, right+1)
    	prime := make([]int, right+1)
    	for i := 2; i <= right; i++ {
    		if !st[i] {
    			prime[cnt] = i
    			cnt++
    		}
    		for j := 0; prime[j] <= right/i; j++ {
    			st[prime[j]*i] = true
    			if i%prime[j] == 0 {
    				break
    			}
    		}
    	}
    	i, j := -1, -1
    	for k := 0; k < cnt; k++ {
    		if prime[k] >= left && prime[k] <= right {
    			if i == -1 {
    				i = k
    			}
    			j = k
    		}
    	}
    	ans := []int{-1, -1}
    	if i == j || i == -1 {
    		return ans
    	}
    	mi := 1 << 30
    	for k := i; k < j; k++ {
    		d := prime[k+1] - prime[k]
    		if d < mi {
    			mi = d
    			ans[0], ans[1] = prime[k], prime[k+1]
    		}
    	}
    	return ans
    }
    

All Problems

All Solutions