Sieve of Eratosthenes to solve a Leetcode problem II

Many years ago I used the Sieve of Eratosthenes to solve a LC problem. Here is another one. The Sieve allows us to calculate all primes between 1..N in O(N)-time, and O(N)-space. Calculate all non-primes in the very first beginning, then just proceed to execute the calculation asked. Code is down below, Happy New Year, ACC.

(1) Closest Prime Numbers in Range - LeetCode

2523. Closest Prime Numbers in Range

Medium

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

public class Solution {
    private static Hashtable primeCache = null;

    public int[] ClosestPrimes(int left, int right)
    {
        if (Solution.primeCache == null)
        {
            Solution.primeCache = new Hashtable();
            Solution.primeCache.Add(1, true);

            int MAX = 1000000;
            for (int i = 2; i <= Math.Sqrt(MAX); i++)
            {
                for (int j = i; i * j <= MAX; j++)
                {
                    if (!Solution.primeCache.ContainsKey(i * j)) Solution.primeCache.Add(i * j, true);
                }
            }
        }

        int min = Int32.MaxValue;
        int p1 = -1;
        int p2 = -1;

        int previousPrime = -1;
        for (int i = left; i <= right; i++)
        {
            if (!Solution.primeCache.ContainsKey(i))
            {
                if (previousPrime == -1) previousPrime = i;
                else
                {
                    if (i - previousPrime < min)
                    {
                        min = i - previousPrime;
                        p1 = previousPrime;
                        p2 = i;
                    }
                    previousPrime = i;
                }
            }
        }

        if(p1 != -1 && p2 != -1) return new int[] {p1, p2 };
        return new int[] { -1, -1 };
    }
}