Count of cells in a matrix whose adjacent cells’s sum is prime Number
Given a M x N matrix mat[][], the task is to count the number of cells which have the sum of its adjacent cells equal to a prime number. For a cell x[i][j], only x[i+1][j], x[i-1][j], x[i][j+1] and x[i][j-1] are the adjacent cells.
Examples:
Input : mat[][] = {{1, 3}, {2, 5}}
Output :2
Explanation: Only the cells mat[0][0] and mat[1][1] satisfying the condition.
i.e for mat[0][0]:(3+2) = 5, for mat[1][1]: (3+2) = 5
Input : mat[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}
Output : 6
Explanation: Cells mat[0][0], mat[0][2], mat[0][3], mat[1][3], mat[2][2] and mat[2][3] are satisfying the condition.
Prerequisites: Sieve of Eratosthenes
Approach:
- Precompute and store the prime numbers using Sieve.
- Iterate the entire matrix and for each cell find the sum of all adjacent cells.
- If the sum of adjacent cells equal to a prime number then increments the count.
- Return the value of the count.
Below is the implementation of the above approach.
C++
// CPP program to find the cells whose // adjacent cells's sum is prime Number #include <bits/stdc++.h> using namespace std; #define MAX 100005 bool prime[MAX]; void SieveOfEratosthenes() { // Create a boolean array "prime[0..MAX-1]" // and initialize all entries it as true. // A value in prime[i] will finally // be false if i is Not a prime, else true. memset (prime, true , sizeof (prime)); prime[0] = prime[1] = false ; for ( int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p // greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i < MAX; i += p) prime[i] = false ; } } } // Function to count the cells having // adjacent cell's sum // is equal to prime int PrimeSumCells(vector<vector< int > >& mat) { int count = 0; int N = mat.size(); int M = mat[0].size(); // Traverse for all the cells for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { int sum = 0; // i-1, j if (i - 1 >= 0) sum += mat[i - 1][j]; // i+1, j if (i + 1 < N) sum += mat[i + 1][j]; // i, j-1 if (j - 1 >= 0) sum += mat[i][j - 1]; // i, j+1 if (j + 1 < M) sum += mat[i][j + 1]; // If the sum is a prime number if (prime[sum]) count++; } } // Return the count return count; } // Driver Program int main() { SieveOfEratosthenes(); vector<vector< int > > mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } }; // Function call cout << PrimeSumCells(mat) << endl; } |
Java
// Java program to find the cells whose // adjacent cells's sum is prime Number class GFG{ static final int MAX = 100005 ; static boolean []prime = new boolean [MAX]; static void SieveOfEratosthenes() { // Create a boolean array "prime[0..MAX-1]" // and initialize all entries it as true. // A value in prime[i] will finally // be false if i is Not a prime, else true. for ( int i = 0 ; i < prime.length; i++) prime[i] = true ; prime[ 0 ] = prime[ 1 ] = false ; for ( int p = 2 ; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p // greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i < MAX; i += p) prime[i] = false ; } } } // Function to count the cells having // adjacent cell's sum // is equal to prime static int PrimeSumCells( int [][]mat) { int count = 0 ; int N = mat.length; int M = mat[ 0 ].length; // Traverse for all the cells for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M; j++) { int sum = 0 ; // i-1, j if (i - 1 >= 0 ) sum += mat[i - 1 ][j]; // i+1, j if (i + 1 < N) sum += mat[i + 1 ][j]; // i, j-1 if (j - 1 >= 0 ) sum += mat[i][j - 1 ]; // i, j+1 if (j + 1 < M) sum += mat[i][j + 1 ]; // If the sum is a prime number if (prime[sum]) count++; } } // Return the count return count; } // Driver Code public static void main(String[] args) { SieveOfEratosthenes(); int [][]mat = { { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 }, { 9 , 10 , 11 , 12 } }; // Function call System.out.print(PrimeSumCells(mat) + "\n" ); } } // This code is contributed by sapnasingh4991 |
Python3
# Python 3 program to # find the cells whose # adjacent cells's # sum is prime Number MAX = 100005 prime = [ True ] * MAX def SieveOfEratosthenes(): # Create a boolean array "prime[0..MAX-1]" # and initialize all entries it as true. # A value in prime[i] will finally # be false if i is Not a prime, else true. global prime prime[ 0 ] = prime[ 1 ] = False p = 2 while p * p < MAX : # If prime[p] is not changed, # then it is a prime if (prime[p] = = True ): # Update all multiples of p # greater than or # equal to the square of it # numbers which are multiple of # p and are less than p^2 are # already been marked. for i in range (p * p, MAX , p): prime[i] = False p + = 1 # Function to count the # cells having adjacent # cell's sum is equal to prime def PrimeSumCells(mat): count = 0 N = len (mat) M = len (mat[ 0 ]) # Traverse for all the cells for i in range (N): for j in range (M): sum = 0 # i - 1, j if (i - 1 > = 0 ): sum + = mat[i - 1 ][j] # i + 1, j if (i + 1 < N): sum + = mat[i + 1 ][j] # i, j - 1 if (j - 1 > = 0 ): sum + = mat[i][j - 1 ] # i, j + 1 if (j + 1 < M): sum + = mat[i][j + 1 ] # If the sum is a prime number if (prime[ sum ]): count + = 1 # Return the count return count # Driver code if __name__ = = "__main__" : SieveOfEratosthenes() mat = [[ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 9 , 10 , 11 , 12 ]] # Function call print (PrimeSumCells(mat)) # This code is contributed by Chitranayal |
C#
// C# program to find the cells whose // adjacent cells's sum is prime Number using System; class GFG{ static readonly int MAX = 100005; static bool []prime = new bool [MAX]; static void SieveOfEratosthenes() { // Create a bool array "prime[0..MAX-1]" // and initialize all entries it as true. // A value in prime[i] will finally // be false if i is Not a prime, else true. for ( int i = 0; i < prime.Length; i++) prime[i] = true ; prime[0] = prime[1] = false ; for ( int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p // greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i < MAX; i += p) prime[i] = false ; } } } // Function to count the cells having // adjacent cell's sum // is equal to prime static int PrimeSumCells( int [,]mat) { int count = 0; int N = mat.GetLength(0); int M = mat.GetLength(1); // Traverse for all the cells for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { int sum = 0; // i-1, j if (i - 1 >= 0) sum += mat[i - 1, j]; // i+1, j if (i + 1 < N) sum += mat[i + 1, j]; // i, j-1 if (j - 1 >= 0) sum += mat[i, j - 1]; // i, j+1 if (j + 1 < M) sum += mat[i, j + 1]; // If the sum is a prime number if (prime[sum]) count++; } } // Return the count return count; } // Driver Code public static void Main(String[] args) { SieveOfEratosthenes(); int [,]mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } }; // Function call Console.Write(PrimeSumCells(mat) + "\n" ); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript program to find the cells whose // adjacent cells's sum is prime Number let MAX = 100005 let prime = new Array(MAX); function SieveOfEratosthenes() { // Create a boolean array "prime[0..MAX-1]" // and initialize all entries it as true. // A value in prime[i] will finally // be false if i is Not a prime, else true. prime.fill( true ) prime[0] = prime[1] = false ; for (let p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p // greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (let i = p * p; i < MAX; i += p) prime[i] = false ; } } } // Function to count the cells having // adjacent cell's sum // is equal to prime function PrimeSumCells(mat) { let count = 0; let N = mat.length; let M = mat[0].length; // Traverse for all the cells for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { let sum = 0; // i-1, j if (i - 1 >= 0) sum += mat[i - 1][j]; // i+1, j if (i + 1 < N) sum += mat[i + 1][j]; // i, j-1 if (j - 1 >= 0) sum += mat[i][j - 1]; // i, j+1 if (j + 1 < M) sum += mat[i][j + 1]; // If the sum is a prime number if (prime[sum]) count++; } } // Return the count return count; } // Driver Program SieveOfEratosthenes(); let mat = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ]; // Function call document.write(PrimeSumCells(mat) + "<br>" ); // This code is contributed by gfgking </script> |
6
Time Complexity: O(N*M)
Auxiliary Space: O(MAX)