Count the number of rows and columns in given Matrix having all primes

0 0 5 minutes read

Given a 2D matrix arr[] of size N*M, the task is to find the number of rows and columns having all primes.

Examples:

Input: arr[]= { { 2, 5, 7 }, { 3, 10, 4 }, { 11, 13, 17 } };
Output: 3
Explanation:
2 Rows: {2, 5, 7}, {11, 13, 17}
1 Column: {2, 3, 11}

Input: arr[]={ { 1, 4 }, { 4, 6 } }
Output: 0

Approach: Follow the below steps to solve this problem:

Apply the Sieve algorithm to find all prime numbers.
Traverse all elements row-wise to find the number of rows having all primes.
Apply the above step for all columns.
Return the answer according to the above observation.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 5000
 
bool prime[MAXN + 1];
 
// Sieve to find prime numbers
void SieveOfEratosthenes(int n)
{
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++) {
 
        if (prime[p] == true) {
 
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
}
 
// Function to find the number of rows
// and columns having all primes
int primeRowCol(vector<vector<int> >& arr)
{
    int N = arr.size();
    int M = arr[0].size();
 
    SieveOfEratosthenes(MAXN);
 
    int cnt = 0;
 
    // Counting Rows with all primes
    for (int i = 0; i < N; i++) {
 
        bool flag = 1;
        for (int j = 0; j < M; ++j) {
            if (!prime[arr[i][j]]) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            cnt += 1;
        }
    }
 
    // Counting Cols with all primes
    for (int i = 0; i < M; i++) {
 
        bool flag = 1;
        for (int j = 0; j < N; ++j) {
            if (!prime[arr[j][i]]) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            cnt += 1;
        }
    }
 
    return cnt;
}
 
// Driver Code
int main()
{
 
    vector<vector<int> > arr
        = { { 2, 5, 7 }, { 3, 10, 4 }, { 11, 13, 17 } };
    cout << primeRowCol(arr);
}

Java

// Java program for the above approach
class GFG {
 
  static int MAXN = 5000;
  static boolean[] prime = new boolean[MAXN + 1];
 
  // Sieve to find prime numbers
  static void SieveOfEratosthenes(int n) {
    for (int i = 0; i < MAXN; i++) {
      prime[i] = true;
    }
 
    for (int p = 2; p * p <= n; p++) {
 
      if (prime[p] == true) {
 
        for (int i = p * p; i <= n; i += p) {
          prime[i] = false;
        }
      }
    }
  }
 
  // Function to find the number of rows
  // and columns having all primes
  static int primeRowCol(int[][] arr) {
    int N = arr.length;
    int M = arr[0].length;
 
    SieveOfEratosthenes(MAXN);
 
    int cnt = 0;
 
    // Counting Rows with all primes
    for (int i = 0; i < N; i++) {
 
      boolean flag = true;
      for (int j = 0; j < M; ++j) {
        if (!prime[arr[i][j]]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        cnt += 1;
      }
    }
 
    // Counting Cols with all primes
    for (int i = 0; i < M; i++) {
 
      boolean flag = true;
      for (int j = 0; j < N; ++j) {
        if (!prime[arr[j][i]]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        cnt += 1;
      }
    }
 
    return cnt;
  }
 
  // Driver Code
  public static void main(String args[]) {
 
    int[][] arr = { { 2, 5, 7 }, { 3, 10, 4 }, { 11, 13, 17 } };
    System.out.println(primeRowCol(arr));
  }
}
 
// This code is contributed by gfgking

Python3

# Python 3 program for the above approach
MAXN = 5000
 
prime = [True]*(MAXN + 1)
 
# Sieve to find prime numbers
def SieveOfEratosthenes(n):
 
    p = 2
    while p * p <= n:
 
        if (prime[p] == True):
 
            for i in range(p * p, n + 1, p):
                prime[i] = False
 
        p += 1
 
# Function to find the number of rows
# and columns having all primes
def primeRowCol(arr):
 
    N = len(arr)
    M = len(arr[0])
 
    SieveOfEratosthenes(MAXN)
 
    cnt = 0
 
    # Counting Rows with all primes
    for i in range(N):
 
        flag = 1
        for j in range(M):
            if (not prime[arr[i][j]]):
                flag = 0
                break
 
        if (flag):
            cnt += 1
 
    # Counting Cols with all primes
    for i in range(M):
 
        flag = 1
        for j in range(N):
            if (not prime[arr[j][i]]):
                flag = 0
                break
 
        if (flag):
            cnt += 1
 
    return cnt
 
# Driver Code
if __name__ == "__main__":
 
    arr = [[2, 5, 7], [3, 10, 4], [11, 13, 17]]
    print(primeRowCol(arr))
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
class GFG
{
 
static int MAXN = 5000;
static bool []prime = new bool[MAXN + 1];
 
// Sieve to find prime numbers
static void SieveOfEratosthenes(int n)
{
    for(int i = 0; i < MAXN; i++){
        prime[i] = true;
    }
 
    for (int p = 2; p * p <= n; p++) {
 
        if (prime[p] == true) {
 
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
}
 
// Function to find the number of rows
// and columns having all primes
static int primeRowCol(int [,]arr)
{
    int N = arr.GetLength(0);
    int M = arr.GetLength(1);
 
    SieveOfEratosthenes(MAXN);
 
    int cnt = 0;
 
    // Counting Rows with all primes
    for (int i = 0; i < N; i++) {
 
        bool flag = true;
        for (int j = 0; j < M; ++j) {
            if (!prime[arr[i, j]]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cnt += 1;
        }
    }
 
    // Counting Cols with all primes
    for (int i = 0; i < M; i++) {
 
        bool flag = true;
        for (int j = 0; j < N; ++j) {
            if (!prime[arr[j, i]]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cnt += 1;
        }
    }
 
    return cnt;
}
 
// Driver Code
public static void Main()
{
 
    int [,]arr
        = { { 2, 5, 7 }, { 3, 10, 4 }, { 11, 13, 17 } };
    Console.Write(primeRowCol(arr));
}
}
 
// This code is contributed by Samim Hosdsain Mondal.

Javascript

  <script>
      // JavaScript code for the above approach 
      let MAXN = 5000
      let prime = new Array(MAXN + 1).fill(true);
 
      // Sieve to find prime numbers
      function SieveOfEratosthenes(n)
      {
          for (let p = 2; p * p <= n; p++) 
          {
              if (prime[p] == true) {
 
                  for (let i = p * p; i <= n; i += p) {
                      prime[i] = false;
                  }
              }
          }
      }
 
      // Function to find the number of rows
      // and columns having all primes
      function primeRowCol(arr) {
          let N = arr.length;
          let M = arr[0].length;
 
          SieveOfEratosthenes(MAXN);
 
          let cnt = 0;
 
          // Counting Rows with all primes
          for (let i = 0; i < N; i++) {
 
              let flag = 1;
              for (let j = 0; j < M; ++j) {
                  if (!prime[arr[i][j]]) {
                      flag = 0;
                      break;
                  }
              }
              if (flag) {
                  cnt += 1;
              }
          }
 
          // Counting Cols with all primes
          for (let i = 0; i < M; i++) {
 
              let flag = 1;
              for (let j = 0; j < N; ++j) {
                  if (!prime[arr[j][i]]) {
                      flag = 0;
                      break;
                  }
              }
              if (flag) {
                  cnt += 1;
              }
          }
 
          return cnt;
      }
 
      // Driver Code
      let arr = [[2, 5, 7], [3, 10, 4], [11, 13, 17]];
      document.write(primeRowCol(arr));
 
// This code is contributed by Potta Lokesh
  </script>

Output

Time Complexity: O(N*M)
Auxiliary Space: O(MAXN)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!