CODEWITHSUNDEEP
c++algorithmmatrix
A Big Ball Of Lettuce
A Big Ball Of Lettuce

Reputation: 313

unsorted matrix search algorithm

is there a suitable algorithm that allows a program to search through an unsorted matrix in search of the biggest prime number within. The matrix is of size m*n and may be populated with other prime numbers and non-primes. The search must find the biggest prime.

I have studied the divide and conquer algorithms, and binary trees, and step-wise searches, but all of these deal with sorted matrices.

Upvotes: 1

Views: 1423

Answers (2)

Jakiša Tomić
Jakiša Tomić

Reputation: 290

First of all, it doesn't matter if you are using m * n matrix or vector with m * n elements. Generally speaking, you will have to visit each matrix element at least once, as it is not sorted. There are few hints to make process faster.

  1. If it is big matrix, you should visit elements row by row (and not column by column) as matrix is stored that way in memory so that elements from the same row will likely be in the cache once you access one of them.

  2. Testing number's primeness is the most costly part of your task so if numbers in matrix are not too big, you can use Eratosthenes' sieve algorithm to make lookup of prime numbers in advance. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

  3. If you don't use Eratosthenes' sieve, maybe it will be beneficial if you sort your numbers before algorithm so that you can test numbers from the greatest to the smallest. In that case, your algorithm can stop once the first prime number is found. If you don't sort it, you will have to test all numbers, which is probably slowest method.

Upvotes: 1

Jake
Jake

Reputation: 81

You could do this:

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

Upvotes: 0

Related Questions