Cuente el número de filas y columnas en una Array dada que tiene todos los números primos

Posted on by Rudeus Greyrat

Dada una array 2D arr[] de tamaño N*M , la tarea es encontrar el número de filas y columnas que tienen todos números primos.

Ejemplos:

Entrada: arr[]= { { 2, 5, 7 }, { 3, 10, 4 }, { 11, 13, 17 } };
Salida: 3
Explicación: 
2 Filas: {2, 5, 7}, {11, 13, 17}
1 Columna: {2, 3, 11}

Entrada: arr[]={ { 1, 4 }, { 4, 6 } }
Salida: 0

Enfoque: siga los pasos a continuación para resolver este problema:

  1. Aplica el algoritmo Sieve para encontrar todos los números primos.
  2. Recorra todos los elementos en forma de fila para encontrar el número de filas que tienen todos los números primos.
  3. Aplique el paso anterior para todas las columnas.
  4. Devuelva la respuesta de acuerdo con la observación anterior.

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

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>
Producción

3

Complejidad de tiempo: O(N*M) 
Espacio auxiliar: O(max(arr))

Publicación traducida automáticamente

Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *