计算所有素数子矩阵的数量

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

- NewUser

---

你能展示一下你的尝试吗？ - Mad Physicist

看起来这是一个动态规划算法的好候选。一个2x2矩阵实际上是4个相邻的1x1矩阵，这意味着如果你为较小的矩阵解决问题并保存相关信息，它应该会逐步构建起来。 - twain249

提示1：每个2x2子矩阵包含四个1x1子矩阵。每个3x3子矩阵包含四个2x2子矩阵。提示2：埃拉托色尼筛法 - user3386109

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

- גלעד ברקן

Answer 2

想法

首先，将您的矩阵转换为0/1矩阵， 对于非素数使用0，对于素数使用1。

现在，您有一个由1组成的“表面”。您可以在这个表面上放多少个正方形呢？ 考虑一下：如果您从(0,0)开始拥有一个3*3的由1组成的正方形，那么您已经知道(1,0)-(2,1)、(0,1)-(1,2)和(1,1)-(2,2)这些正方形都由1组成，因此您不需要再次检查这些正方形。 因此，您将寻找以(1,0)、(0,1)或(1,1)为起点的1组成的正方形，只有当它们大于2*2时才寻找。 想象一下，以(1,0)为起点的最大正方形大小为3*3，但其他两个是2*2。您可以忽略后者（它们没有添加任何新内容），但必须添加新的3*3正方形并删除与之前正方形重叠的部分。

这可以概括如下：

• 在矩阵M中存储以(0,0)为起点的最大正方形大小
• 令N = 大小为M[0,0]的正方形中子正方形的数量
• 对于每个(r,c)，从左到右，从上到下：
  • 从M中获取以(r-1,c)，(r,c-1)或(r-1,c-1)为起点的最大正方形大小，称之为K
    • 计算以(r,c)为起点的最大正方形大小（从K-1开始）
    • 如果M[r,c] = K-1，则不进行任何操作
    • 如果M[r,c] > K-1，更新N： N += 大小为M[r,c]的正方形中子正方形的数量 - 大小为K-1的正方形中子正方形的数量

关键在于“计算从(r,c)开始的最大正方形尺寸（从K-1开始）”将避免许多比较。

伪代码（类似Python）

首先，注意到大小为k的正方形包含k^2个大小为1的正方形，(k-1)^2个大小为2的正方形，...，一个大小为k的正方形。这是一个众所周知的总和（我从维基百科上得出了结果！）：

subsquares_count(k) = 1/6*k + 1/2*k^2 + 1/3*k^3

计算以 (r, c) 为起点的最大正方形的大小并不困难。我在 K 处添加了一个开始：

def largest_square_size(m, r, c, K):
    k = K
    while k<n:
        # check the border
        for l in 0..k:
            if m[r+k, c+l] == 0 or m[r+l, c+k] == 0: # consider the left and bottom borders
                break while
        if m[r+k, c+k] == 0 # don't forget the corner
            break while
        k += 1
    return k

现在，主循环的草图：

for r in 0..n:
    for c in 0..n: 
        K = max(M[r-1,c-1], M[r-1,c], M[r,c-1]) - 1 # add boundary check, K = 0 if r,c = 0,0
        M[r,c] = largest_square_size(m, r, c, K)
        if M[r,c] > K:
            N += subsquares_count(M[0,0]) - subsquares_count(K)

免责声明：我没有测试过这个代码，可能存在一些边缘情况，但我认为它是正确的。

显然不太优化，因为有些位置可能会被检查多次，但它应该表现良好。

- jferard