Recuento de celdas en una array cuya suma de celdas adyacentes es número primo

Dada una array M x N mat[][] , la tarea es contar el número de celdas que tienen la suma de sus celdas adyacentes igual a un número primo . Para una celda x[i][j] , solo x[i+1][j], x[i-1][j], x[i][j+1] y x[i][j-1 ] son ​​las celdas adyacentes.
Ejemplos: 

Entrada: mat[][] = {{1, 3}, {2, 5}} 
Salida: 2 
Explicación: Solo las celdas mat[0][0] y mat[1][1] cumplen la condición. 
es decir, para mat[0][0]:(3+2) = 5, para mat[1][1]: (3+2) = 5
Entrada: mat[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}} 
Salida: 6 
Explicación: Celdas mat[0][0], mat[0][2], mat[0][ 3], mat[1][3], mat[2][2] y mat[2][3] cumplen la condición. 
 

Prerrequisitos: Tamiz de Eratóstenes 
Enfoque:  

• Precalcule y almacene los números primos usando Sieve.
• Iterar toda la array y para cada celda encontrar la suma de todas las celdas adyacentes.
• Si la suma de las celdas adyacentes es igual a un número primo, entonces se incrementa el conteo.
• Devuelve el valor del conteo.

A continuación se muestra la implementación del enfoque anterior.
 

// 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 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

# 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# 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

<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

Complejidad de tiempo : O(N*M)

Espacio Auxiliar : O(MAX)