Miller-Rabin Primality Test and Caching II

A bit overkill to use MRP here. Also, there is probably a way to do it a little faster by scanning from left, then right, and stopping at the first prime number from each side. Code is down below, cheers, ACC.

3115. Maximum Prime Difference

Medium

You are given an integer array nums.

Return an integer that is the maximum distance between the indices of two (not necessarily different) prime numbers in nums.

 

Example 1:

Input: nums = [4,2,9,5,3]

Output: 3

Explanation: nums[1], nums[3], and nums[4] are prime. So the answer is |4 - 1| = 3.

Example 2:

Input: nums = [4,8,2,8]

Output: 0

Explanation: nums[2] is prime. Because there is just one prime number, the answer is |2 - 2| = 0.

 

Constraints:

• 1 <= nums.length <= 3 * 105
• 1 <= nums[i] <= 100
• The input is generated such that the number of prime numbers in the nums is at least one.

public class Solution {
    public static Hashtable primes100 = null;
    public int MaximumPrimeDifference(int[] nums)
    {
        int min = Int32.MaxValue;
        int max = Int32.MinValue;

        if (primes100 == null)
        {
            primes100 = new Hashtable();
            for (int i = 1; i <= 100; i++)
                if (IsPrimeMillerRabin(i)) primes100.Add(i, true);
        }

        for (int i = 0; i < nums.Length; i++)
        {
            if (primes100.ContainsKey(nums[i]))
            {
                min = Math.Min(min, i);
                max = Math.Max(max, i);
            }
        }

        return max - min;
    }
    
        public bool IsPrimeMillerRabin(BigInteger n)
    {
        //It does not work well for smaller numbers, hence this check
        int SMALL_NUMBER = 1000;

        if (n <= SMALL_NUMBER)
        {
            return IsPrime(n);
        }

        int MAX_WITNESS = 100;
        for (long i = 2; i <= MAX_WITNESS; i++)
        {
            if (IsPrime(i) && Witness(i, n) == 1)
            {
                return false;
            }
        }

        return true;
    }

    public BigInteger SqRtN(BigInteger N)
    {
        /*++
         *  Using Newton Raphson method we calculate the
         *  square root (N/g + g)/2
         */
        BigInteger rootN = N;
        int count = 0;
        int bitLength = 1;
        while (rootN / 2 != 0)
        {
            rootN /= 2;
            bitLength++;
        }
        bitLength = (bitLength + 1) / 2;
        rootN = N >> bitLength;

        BigInteger lastRoot = BigInteger.Zero;
        do
        {
            if (lastRoot > rootN)
            {
                if (count++ > 1000)                   // Work around for the bug where it gets into an infinite loop
                {
                    return rootN;
                }
            }
            lastRoot = rootN;
            rootN = (BigInteger.Divide(N, rootN) + rootN) >> 1;
        }
        while (!((rootN ^ lastRoot).ToString() == "0"));
        return rootN;
    }

    public bool IsPrime(BigInteger n)
    {
        if (n <= 1)
        {
            return false;
        }

        if (n == 2)
        {
            return true;
        }

        if (n % 2 == 0)
        {
            return false;
        }

        for (int i = 3; i <= SqRtN(n) + 1; i += 2)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
        return true;
    }

    private int Witness(long a, BigInteger n)
    {
        BigInteger t, u;
        BigInteger prev, curr = 0;
        BigInteger i;
        BigInteger lln = n;

        u = n / 2;
        t = 1;
        while (u % 2 == 0)
        {
            u /= 2;
            t++;
        }

        prev = BigInteger.ModPow(a, u, n);
        for (i = 1; i <= t; i++)
        {
            curr = BigInteger.ModPow(prev, 2, lln);
            if ((curr == 1) && (prev != 1) && (prev != lln - 1)) return 1;
            prev = curr;
        }
        if (curr != 1) return 1;
        return 0;
    }
}