非排序矩阵搜索算法

Question

有没有合适的算法，允许程序在一个未排序的矩阵中搜索最大的质数。该矩阵的大小为m*n，并且可以用其他素数和非素数填充。搜索必须找到最大的素数。

我已经研究了分治算法、二叉树和分步搜索，但所有这些都是处理排序矩阵的。

Answer 1

首先，如果您使用的是m*n矩阵或具有m*n元素的向量，这并不重要。一般来说，您必须至少访问每个矩阵元素一次，因为它没有排序。有几个提示可以让过程更快。

1. 如果是大矩阵，你应该逐行访问元素(而不是逐列访问)，因为矩阵是以这种方式存储在内存中的，这样一旦你访问了其中的一个，来自同一行的元素很可能就会出现在缓存中。
2. 测试数字的素性是你任务中最昂贵的部分，所以如果矩阵中的数字不是太大，你可以使用Eratosthenes的筛子算法提前查找质数。如果你不使用Eratosthenes筛子，也许在算法之前对你的数字进行排序会很有帮助，这样你就可以从最大的到最小的测试数字。https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
3. If。在这种情况下，一旦找到第一个质数，您的算法就可以停止。如果你不对它排序，你将不得不测试所有的数字，这可能是最慢的方法。

Answer 2

你可以这样做：

for (int i = 0; i < m; m++)
{
    for (int j = 0; j < n; j++)
    {
       if ((array[i][j] == *a prime number*) 
           && (array[i][j] > biggestPrime))
       {
           biggestPrime = array[i][j];
       }
    }
}