Counting sub matrix with all prime numbers

Question

I am given an NxN matrix. A submatrix is considered special if it satisfies the following condition:

1. It must be a square in shape
2. All numbers must be prime.

I have to count the total number of submatrices of the given matrix that satisfies the following criteria.

For example, let sample input be=>

3
3 5 6
8 3 2
3 5 2

Sample output: 8

Explanation:

• 1x1: There are 7 prime numbers and every 1x1 matrix contains 1 prime number
• 2x2: only the bottom right submatrix contains all primes
• 3x3: No 3x3matrix satisfies these criteria

So the final answer is (7+1+0)=8

I recently came across this question in an interview. And I could come up with a brute force solution. What is the best way to solve this question?

[UPDATE] I have pasted my attempt to solve the problem.

class TestClass 
{
    public static boolean isPrime(int n)
    {
        if(n<2)
            return false;
        for(int i=2;i<=Math.sqrt(n);i++)
        {
            if(n%i==0)
                return false;
        }
        return true;
    }
    public static boolean scan_matrix(boolean a[][], int start_i, int start_j, int n)
    {
        for(int i=start_i;i<start_i+n;i++)
        {
            for(int j=start_j;j<start_j+n;j++)
            {
                if(!a[i][j])
                    return false;
            }
        }
        return true;
    }
    public static int count_valid_matrix(boolean a[][], int n, int N)
    {
        int result = 0;
        for(int start_i=0;start_i<=N-n;start_i++)
        {
            for(int start_j=0;start_j<=N-n;start_j++)
            {
                if(scan_matrix(a, start_i, start_j, n))
                    result += 1;
            }
        }
        return result;
    }

    public static void main(String args[]) throws Exception
    {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        boolean a[][] = new boolean[N][N];
        int result = 0;
        for(int i=0;i<N; i++)
        {
            for(int j=0;j<N;j++)
            {
                int num = s.nextInt();
                a[i][j] = isPrime(num);
                if(a[i][j])
                    result += 1;
            }
        }
        int n = 2;
        while(n<N)
        {
            result += count_valid_matrix(a, n, N);
            n++;
        }
        System.out.println(result);
    }
}

Answer 1

Here's part of one possible formulation. Let is_special(I, J, W) represent whether the matrix cell m(I, J) is the bottom right corner of a valid square of width W. Then:

is_special(I, J, 1) ->
  is_prime( m(I, J) );

is_special(I, J, W) ->
  (I >= W - 1 andalso                     % assuming I starts from 0
    (J >= W - 1 andalso                   % assuming J starts from 0
      (is_special(I, J, W - 1) and
       is_special(I - 1, J, W - 1) and
       is_special(I, J - 1, W - 1) and
       is_special(I - 1, J - 1, W - 1)))).