Maths is a very fun subject to study, and so is programming, but what happens when these two are combined together? Today, we will discuss one such problem, i.e., Find Prime numbers in a 2D Array(Matrix), where your concepts related to programming and maths would be judged. Let’s understand the problem better.
We have been given a 2D matrix ‘MAT’. Our task is to find and print the prime numbers present in the matrix along with their positions.
Let’s see the following example for a better understanding.
‘MAT’ =
1 2 3
4 5 6
7 8 9
Output
1 2 2
1 3 3
2 2 5
3 1 7
Explanation
As 2,3,5,7 are prime numbers. They are printed along with their positions. For example, 2 is located in the first row and second column, so we print
1 2 2.
Similarly, for 5, it is located in the second row and second column, so we print
2 2 5. And so on.
Intuition
The approach is quite simple we will iterate over the matrix and check whether a number is prime or not. If it is prime, we will print it along with its row and column.
Naive Approach
Now we have two methods to check whether a number is prime or not. First, we will solve it using the naive way mentioned here.
Let’s see the code for both approaches.
C++ Implementation
#include <iostream>
#include<vector>
using namespace std;
// Brute force to check whether the number ‘N’ is prime or not.
bool isPrime(int N)
{
if (N == 1)
{
return false;
}
// Checking if it is divisible by any other number.
for (int i = 2; i * i <= N; i++)
{
if (N % i == 0)
{
return false;
}
}
return true;
}
// Function that will print all the prime numbers in the matrix, ‘MAT’.
void primeWithLocation(vector<vector<int>> &mat)
{
// Traverse the matrix
for (int i = 0; i < mat.size(); i++)
{
for (int j = 0; j < mat[0].size(); j++)
{
// Check if the element is prime or not.
if (isPrime(mat[i][j]))
{
cout << i + 1 << " " << j + 1 << " " <<
mat[i][j] << endl;
}
}
}
}
int main()
{
int m, n;
cin >> m >> n;
vector<vector<int>> mat(m, vector<int> (n, 0));
// Taking Input.
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cin >> mat[i][j];
}
}
primeWithLocation(mat);
return 0;
}
O((M * N) ^ sqrt(X)), where ‘M’ is the size of the row and ‘N’ is the size of the column, and ‘X’ is the maximum number present in the matrix.
As we are looping every element in the matrix, it will cost us O(M * N) time. Also, we are checking whether that element is prime or not, which will cost us O(sqrt(X)) time in the worst case. Thus the overall time complexity becomes O((M * N) * sqrt(X)).
Now we will use the method of the sieve of Eratosthenes discussed here to test the primality. After populating the ‘PRIME’ array, we can check whether is prime or not in constant time just by a lookup in the ‘PRIME’ array.
#include <iostream>
#include <vector>
using namespace std;
vector<int> primes;
// Function to implement Sieve Of Eratosthenes
void sieveOfEratosthenes()
{
int r = 10001;
primes.assign(r + 1, 1);
primes[1] = 0;
int i = 2;
while (i * i <= r)
{
if (primes[i] == 1)
{
int j = i + i;
while (j <= r)
{
primes[j] = 0;
j += i;
}
}
i++;
}
}
// Function that will print our answer.
void primeWithLocation(vector<vector<int>> &mat)
{
// Traverse the matrix
for (int i = 0; i < mat.size(); i++)
{
for (int j = 0; j < mat[0].size(); j++)
{
// Check if the element is prime or not.
if (primes[mat[i][j]])
{
cout << i + 1 << " " << j + 1 << " " <<
mat[i][j] << endl;
}
}
}
}
int main()
{
int m, n;
cin >> m >> n;
vector<vector<int>> mat(m, vector<int> (n, 0));
// Taking Input.
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cin >> mat[i][j];
}
}
// Calling Sieve to generate prime numbers.
sieveOfEratosthenes();
primeWithLocation(mat);
return 0;
}
Input
3 3
1 2 3
4 5 6
7 8 9
Output
1 2 2
1 3 3
2 2 5
3 1 7
Complexity Analysis
Time Complexity
O(M * N), where ‘M’ is the size of the row and ‘N’ is the size of the column.
The time complexity of populating the ‘PRIME’ array using sieveOfEratosthenes() is O(MAXN * log(log(MAXN)))
As we are looping over every element in the matrix and each lookup takes constant time. So, in total, it will cost us O(M * N) time..
Thus the overall time complexity is O((M * N) + (MAXN * log(log(MAXN)))) = O(M * N).
Space Complexity
O(MAXN).
As we are creating an extra array, ‘PRIME’ of primes of size ‘MAXN.’
Prime Numbers are numbers that are divisible only by 1 and themselves.
What is the time complexity of the sieve of Eratosthenes?
The overall time complexity is O(M*N) where M is the number of rows and N is the number of columns.
Conclusion
We saw how we solved the problem ‘Find Prime numbers in a 2D Array (Matrix)’ by both Naive as well as efficient methods, namely Sieve of Eratosthenes. You must be thrilled about learning a new concept but the road to becoming a champ coder is still very long. So check out some of theGuided Pathson topics such asData Structure and Algorithms, Competitive Programming, etc. as well as some Contests and Interview Experiences along with some of the top interview questions from top companies like Amazon, Google, and Microsoftonly onCoding Ninjas Studio.
38+ registered 