Miller-Rabin Primality Test and Caching IV

It is interesting to ask the time complexity of a LC solution to ChatGPT, especially if it involves a complex algorithm like Miller-Rabin Primality Testing. This one is a good example:

Complete Prime Number - LeetCode

You are given an integer num.

A number num is called a Complete Prime Number if every prefix and every suffix of num is prime.

Return true if num is a Complete Prime Number, otherwise return false.

Note:

• A prefix of a number is formed by the first k digits of the number.
• A suffix of a number is formed by the last k digits of the number.
• A prime number is a natural number greater than 1 with only two factors, 1 and itself.
• Single-digit numbers are considered Complete Prime Numbers only if they are prime.

 

Example 1:

Input: num = 23

Output: true

Explanation:

• ​​​​​​​Prefixes of num = 23 are 2 and 23, both are prime.
• Suffixes of num = 23 are 3 and 23, both are prime.
• All prefixes and suffixes are prime, so 23 is a Complete Prime Number and the answer is true.

Example 2:

Input: num = 39

Output: false

Explanation:

• Prefixes of num = 39 are 3 and 39. 3 is prime, but 39 is not prime.
• Suffixes of num = 39 are 9 and 39. Both 9 and 39 are not prime.
• At least one prefix or suffix is not prime, so 39 is not a Complete Prime Number and the answer is false.

Example 3:

Input: num = 7

Output: true

Explanation:

• 7 is prime, so all its prefixes and suffixes are prime and the answer is true.

 

Constraints:

• 1 <= num <= 109

The problem isn't hard especially using M-R Primality Test. When asking for the time complexity, this is what OpenAI gave me:

Notice how fast M-R is, the problem then for a num = 10^9 (and hence d=9) becomes a simple d^4, or in other words the complexity is (LogN)^4. Code is down below, cheers, ACC.

public class Solution {
    public bool CompletePrime(int num)
    {
        string str = num.ToString();
        Primality primality = new Primality();

        for (int i = 0; i < str.Length; i++)
        {
            int nLeft = Int32.Parse(str.Substring(0, i + 1));
            if (!primality.IsPrimeMillerRabin(nLeft)) return false;
            int nRight = Int32.Parse(str.Substring(i));
            if(!primality.IsPrimeMillerRabin(nRight)) return false;
        }

        return true;
    }
}

    public class Primality
    {
        public static HashSet millerRabinCache = new HashSet();

        public bool IsPrimeMillerRabin(BigInteger n)
        {
            if (millerRabinCache.Contains(n)) return true;

            //It does not work well for smaller numbers, hence this check
            int SMALL_NUMBER = 1000;

            if (n <= SMALL_NUMBER)
            {
                bool val = IsPrime(n);
                if (val) millerRabinCache.Add(n);
                return val;
            }

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

            millerRabinCache.Add(n);
            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;
        }
    }