Miller-Rabin Primality Test and Caching

-

Miller-Rabin remains one of the best practical primality testing available, despite the famous Primes is in P from 2003. Miller-Rabin is also a polynomial time algorithm but it is non-deterministic. However, given enough "iterations and witnesses", the non-deterministic aspect is so small that for all practical purposes it becomes deterministic. The implementation below for example has a probability of producing a wrong primality test of 9 x 10 ^ (-58) percent. The problem doesn't really need Miller-Rabin since the numbers are small but it is a good example of how to use it (together with some caching) to solve problems involving prime numbers in a very fast fashion. Code is down below, cheers, ACC.

Most Frequent Prime - LeetCode

3044. Most Frequent Prime
Medium

You are given a m x n 0-indexed 2D matrix mat. From every cell, you can create numbers in the following way:

  • There could be at most 8 paths from the cells namely: east, south-east, south, south-west, west, north-west, north, and north-east.
  • Select a path from them and append digits in this path to the number being formed by traveling in this direction.
  • Note that numbers are generated at every step, for example, if the digits along the path are 1, 9, 1, then there will be three numbers generated along the way: 1, 19, 191.

Return the most frequent prime number greater than 10 out of all the numbers created by traversing the matrix or -1 if no such prime number exists. If there are multiple prime numbers with the highest frequency, then return the largest among them.

Note: It is invalid to change the direction during the move.

 

Example 1:


Input: mat = [[1,1],[9,9],[1,1]]
Output: 19
Explanation: 
From cell (0,0) there are 3 possible directions and the numbers greater than 10 which can be created in those directions are:
East: [11], South-East: [19], South: [19,191].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [19,191,19,11].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [99,91,91,91,91].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [91,91,99,91,91].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [11,19,191,19].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [11,19,19,191].
The most frequent prime number among all the created numbers is 19.

Example 2:

Input: mat = [[7]]
Output: -1
Explanation: The only number which can be formed is 7. It is a prime number however it is not greater than 10, so return -1.

Example 3:

Input: mat = [[9,7,8],[4,6,5],[2,8,6]]
Output: 97
Explanation: 
Numbers greater than 10 created from the cell (0,0) in all possible directions are: [97,978,96,966,94,942].
Numbers greater than 10 created from the cell (0,1) in all possible directions are: [78,75,76,768,74,79].
Numbers greater than 10 created from the cell (0,2) in all possible directions are: [85,856,86,862,87,879].
Numbers greater than 10 created from the cell (1,0) in all possible directions are: [46,465,48,42,49,47].
Numbers greater than 10 created from the cell (1,1) in all possible directions are: [65,66,68,62,64,69,67,68].
Numbers greater than 10 created from the cell (1,2) in all possible directions are: [56,58,56,564,57,58].
Numbers greater than 10 created from the cell (2,0) in all possible directions are: [28,286,24,249,26,268].
Numbers greater than 10 created from the cell (2,1) in all possible directions are: [86,82,84,86,867,85].
Numbers greater than 10 created from the cell (2,2) in all possible directions are: [68,682,66,669,65,658].
The most frequent prime number among all the created numbers is 97.

 

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 6
  • 1 <= mat[i][j] <= 9

public class Solution {
    public static Hashtable notPrime = new Hashtable();
    public static Hashtable primesSet = new Hashtable();

    public bool IsPrimeMillerRabin(BigInteger n)
    {
        if(primesSet.ContainsKey(n)) return true;
        
        //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;
            }
        }
        
        if(!primesSet.ContainsKey(n)) primesSet.Add(n, true);

        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;
    }

    public int MostFrequentPrime(int[][] mat)
    {
        Hashtable primeFrequency = new Hashtable();
        int maxFrequency = 0;
        int maxPrime = -1;

        for (int r = 0; r < mat.Length; r++)
        {
            for (int c = 0; c < mat[r].Length; c++)
            {
                CalculateAllPrimesFromPosition(mat, r, c, primeFrequency, ref maxFrequency, ref maxPrime);
            }
        }

        return maxPrime;
    }

    private void CalculateAllPrimesFromPosition(int[][] mat,
                                                int row,
                                                int col,
                                                Hashtable primeFrequency,
                                                ref int maxFrequency,
                                                ref int maxPrime)
    {
        int number = 0;
        int r = 0;
        int c = 0;

        number = 0;
        for (int i = row; i < mat.Length; i++)
        {
            number = 10 * number + mat[i][col];
            if (number > 10)
            {
                if (primeFrequency.ContainsKey(number)) primeFrequency[number] = (int)primeFrequency[number] + 1;
                else if (!notPrime.ContainsKey(number))
                {
                    if (IsPrimeMillerRabin(number)) primeFrequency.Add(number, 1);
                    else notPrime.Add(number, true);
                }

                if (primeFrequency.ContainsKey(number))
                {
                    if ((int)primeFrequency[number] > maxFrequency)
                    {
                        maxFrequency = (int)primeFrequency[number];
                        maxPrime = number;
                    }
                    else if ((int)primeFrequency[number] == maxFrequency)
                    {
                        maxPrime = Math.Max(maxPrime, number);
                    }
                }
            }
        }

        number = 0;
        for (int i = col; i < mat[0].Length; i++)
        {
            number = 10 * number + mat[row][i];
            if (number > 10)
            {
                if (primeFrequency.ContainsKey(number)) primeFrequency[number] = (int)primeFrequency[number] + 1;
                else if (!notPrime.ContainsKey(number))
                {
                    if (IsPrimeMillerRabin(number)) primeFrequency.Add(number, 1);
                    else notPrime.Add(number, true);
                }

                if (primeFrequency.ContainsKey(number))
                {
                    if ((int)primeFrequency[number] > maxFrequency)
                    {
                        maxFrequency = (int)primeFrequency[number];
                        maxPrime = number;
                    }
                    else if ((int)primeFrequency[number] == maxFrequency)
                    {
                        maxPrime = Math.Max(maxPrime, number);
                    }
                }
            }
        }

        number = 0;
        for (int i = row; i >= 0; i--)
        {
            number = 10 * number + mat[i][col];
            if (number > 10)
            {
                if (primeFrequency.ContainsKey(number)) primeFrequency[number] = (int)primeFrequency[number] + 1;
                else if (!notPrime.ContainsKey(number))
                {
                    if (IsPrimeMillerRabin(number)) primeFrequency.Add(number, 1);
                    else notPrime.Add(number, true);
                }

                if (primeFrequency.ContainsKey(number))
                {
                    if ((int)primeFrequency[number] > maxFrequency)
                    {
                        maxFrequency = (int)primeFrequency[number];
                        maxPrime = number;
                    }
                    else if ((int)primeFrequency[number] == maxFrequency)
                    {
                        maxPrime = Math.Max(maxPrime, number);
                    }
                }
            }
        }

        number = 0;
        for (int i = col; i >= 0; i--)
        {
            number = 10 * number + mat[row][i];
            if (number > 10)
            {
                if (primeFrequency.ContainsKey(number)) primeFrequency[number] = (int)primeFrequency[number] + 1;
                else if (!notPrime.ContainsKey(number))
                {
                    if (IsPrimeMillerRabin(number)) primeFrequency.Add(number, 1);
                    else notPrime.Add(number, true);
                }

                if (primeFrequency.ContainsKey(number))
                {
                    if ((int)primeFrequency[number] > maxFrequency)
                    {
                        maxFrequency = (int)primeFrequency[number];
                        maxPrime = number;
                    }
                    else if ((int)primeFrequency[number] == maxFrequency)
                    {
                        maxPrime = Math.Max(maxPrime, number);
                    }
                }
            }
        }

        number = 0;
        r = row;
        c = col;
        while (r >= 0 && r < mat.Length && c >= 0 && c < mat[r].Length)
        {
            number = 10 * number + mat[r][c];
            if (number > 10)
            {
                if (primeFrequency.ContainsKey(number)) primeFrequency[number] = (int)primeFrequency[number] + 1;
                else if (!notPrime.ContainsKey(number))
                {
                    if (IsPrimeMillerRabin(number)) primeFrequency.Add(number, 1);
                    else notPrime.Add(number, true);
                }

                if (primeFrequency.ContainsKey(number))
                {
                    if ((int)primeFrequency[number] > maxFrequency)
                    {
                        maxFrequency = (int)primeFrequency[number];
                        maxPrime = number;
                    }
                    else if ((int)primeFrequency[number] == maxFrequency)
                    {
                        maxPrime = Math.Max(maxPrime, number);
                    }
                }
            }
            r++;
            c++;
        }

        number = 0;
        r = row;
        c = col;
        while (r >= 0 && r < mat.Length && c >= 0 && c < mat[r].Length)
        {
            number = 10 * number + mat[r][c];
            if (number > 10)
            {
                if (primeFrequency.ContainsKey(number)) primeFrequency[number] = (int)primeFrequency[number] + 1;
                else if (!notPrime.ContainsKey(number))
                {
                    if (IsPrimeMillerRabin(number)) primeFrequency.Add(number, 1);
                    else notPrime.Add(number, true);
                }

                if (primeFrequency.ContainsKey(number))
                {
                    if ((int)primeFrequency[number] > maxFrequency)
                    {
                        maxFrequency = (int)primeFrequency[number];
                        maxPrime = number;
                    }
                    else if ((int)primeFrequency[number] == maxFrequency)
                    {
                        maxPrime = Math.Max(maxPrime, number);
                    }
                }
            }
            r++;
            c--;
        }

        number = 0;
        r = row;
        c = col;
        while (r >= 0 && r < mat.Length && c >= 0 && c < mat[r].Length)
        {
            number = 10 * number + mat[r][c];
            if (number > 10)
            {
                if (primeFrequency.ContainsKey(number)) primeFrequency[number] = (int)primeFrequency[number] + 1;
                else if (!notPrime.ContainsKey(number))
                {
                    if (IsPrimeMillerRabin(number)) primeFrequency.Add(number, 1);
                    else notPrime.Add(number, true);
                }

                if (primeFrequency.ContainsKey(number))
                {
                    if ((int)primeFrequency[number] > maxFrequency)
                    {
                        maxFrequency = (int)primeFrequency[number];
                        maxPrime = number;
                    }
                    else if ((int)primeFrequency[number] == maxFrequency)
                    {
                        maxPrime = Math.Max(maxPrime, number);
                    }
                }
            }
            r--;
            c++;
        }

        number = 0;
        r = row;
        c = col;
        while (r >= 0 && r < mat.Length && c >= 0 && c < mat[r].Length)
        {
            number = 10 * number + mat[r][c];
            if (number > 10)
            {
                if (primeFrequency.ContainsKey(number)) primeFrequency[number] = (int)primeFrequency[number] + 1;
                else if (!notPrime.ContainsKey(number))
                {
                    if (IsPrimeMillerRabin(number)) primeFrequency.Add(number, 1);
                    else notPrime.Add(number, true);
                }

                if (primeFrequency.ContainsKey(number))
                {
                    if ((int)primeFrequency[number] > maxFrequency)
                    {
                        maxFrequency = (int)primeFrequency[number];
                        maxPrime = number;
                    }
                    else if ((int)primeFrequency[number] == maxFrequency)
                    {
                        maxPrime = Math.Max(maxPrime, number);
                    }
                }
            }
            r--;
            c--;
        }
    }
}


Comments

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

Hard Leetcode Problem: Grid Illumination

-
Image
Here is the problem:  https://leetcode.com/problems/grid-illumination/ On a  N x N  grid of cells, each cell  (x, y)  with  0 <= x < N  and  0 <= y < N  has a lamp. Initially, some number of lamps are on.   lamps[i]  tells us the location of the  i -th lamp that is on.  Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals ( similar to a Queen in chess ). For the i-th query  queries[i] = (x, y) , the answer to the query is 1 if the cell (x, y) is illuminated, else 0. After each query  (x, y)  [in the order given by  queries ], we turn off any lamps that are at cell  (x, y)  or are adjacent 8-directionally (ie., share a corner or edge with cell  (x, y) .) Return an array of answers.  Each value  answer[i]  should be equal to the answer of the  i -th query  queries[i] . Example 1: Input: N = 5 , lamps = [[0,0],[4,4]] , queries = [[1,1],[1,0]] Output: [1,0] Explanation: Before performing the first query we have both lamps [0
Read more