java - 计算所有素数的子矩阵

Question

我有一个 NxN 矩阵。如果满足以下条件，则子矩阵被认为是特殊的:

1. 必须是正方形
2. 所有数字都必须是素数。

我必须计算满足以下条件的给定矩阵的子矩阵总数。

例如，让示例输入为=>

3
3 5 6
8 3 2
3 5 2

示例输出:8

解释:

• 1x1:有7个素数，每个1x1矩阵包含1个素数
• 2x2:只有右下角的子矩阵包含所有素数
• 3x3:没有 3x3 矩阵满足这些条件

所以最后的答案是(7+1+0)=8

我最近在一次采访中遇到了这个问题。我可以想出一个蛮力解决方案。解决这个问题的最佳方法是什么？

[更新]我已经粘贴了解决问题的尝试。

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

这是一种可能的表述的一部分。令is_special(I, J, W)表示矩阵单元格m(I, J)是否是宽度为W<的有效正方形的右下角。然后:

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)))).