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 5000bool prime[MAXN + 1];// Sieve to find prime numbersvoid 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 primesint 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 Codeint main(){ vector<vector<int> > arr = { { 2, 5, 7 }, { 3, 10, 4 }, { 11, 13, 17 } }; cout << primeRowCol(arr);} |
Java
// Java program for the above approachclass 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 approachMAXN = 5000prime = [True]*(MAXN + 1)# Sieve to find prime numbersdef 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 primesdef 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 Codeif __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 approachusing System;class GFG{static int MAXN = 5000;static bool []prime = new bool[MAXN + 1];// Sieve to find prime numbersstatic 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 primesstatic 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 Codepublic 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
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
