Cuente los números primos más pequeños a la derecha de cada elemento de la array

Dada una array A[] de tamaño N , la tarea de cada elemento de la array es contar los elementos de la array a su derecha que son más pequeños que él y son primos .

Ejemplos:

Entrada: N = 10, A[] = {5, 5, 17, 9, 12, 15, 11, 7, 39, 3} Salida: 2 1 3 2 3 3 2 1 1 0 
Explicación
Para 
i = 1, los elementos en j = [2, 10] son ​​una respuesta válida. 
Para i = 2, los elementos en j = [10] son ​​una respuesta válida. 
Para i = 3, los elementos en j = [7, 8, 10] son ​​una respuesta válida. 
Para i = 4, los elementos en j = [8, 10] son ​​una respuesta válida. 
Para i = 5, los elementos en j = [7, 8, 10] son ​​una respuesta válida. 
Para i = 6, los elementos en j = [7, 8, 10] son ​​una respuesta válida. 
Para i = 7, los elementos en j = [8, 10] son ​​una respuesta válida. 
Para i = 8, los elementos en j = [10] son ​​una respuesta válida. 
Para i = 9, los elementos en j = [10] son ​​una respuesta válida. 
Para i = 5, ningún elemento está a su derecha. 

Entrada: N = 6, A[] = {43, 3, 5, 7, 2, 41} 
Salida: 5 1 1 1 0 0
Explicación: 
Para i = 1, elementos en j = [2, 3, 4, 5 , 6] son ​​una respuesta válida. 
Para i = 2, los elementos en j = [5] son ​​una respuesta válida. 
Para i = 3, los elementos en j = [5] son ​​una respuesta válida. 
Para i = 4, los elementos en j = [5] son ​​una respuesta válida. 
Para i = 5, no hay respuesta válida. 
Para i = 6, no hay respuesta válida.

Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y, para cada elemento, A[i] , iterar sobre todos los elementos a su derecha y contar la cantidad de elementos menores que A[i] y primos .

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;
 
// Function to check if a
// number is prime or not
bool is_prime(int n)
{
    if (n <= 1)
        return 0;
 
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}
 
// Function to find the count of
// smaller primes on the right
// of each array element
void countSmallerPrimes(int ar[], int N)
{
    for (int i = 0; i < N; i++) {
 
        // Stores the count of
        // smaller primes
        int count = 0;
        for (int j = i + 1; j < N; j++) {
 
            // If A[j] <= A[i] and A[j] is prime
            if (ar[j] <= ar[i] && is_prime(ar[j])) {
 
                // Increase count
                count++;
            }
        }
 
        // Print the count for
        // the current element
        cout << count << " ";
    }
}
 
// Driver Code
int main()
{
    int ar[] = { 43, 3, 5, 7, 2, 41 };
    int N = sizeof ar / sizeof ar[0];
 
    // Function call
    countSmallerPrimes(ar, N);
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function to check if a
// number is prime or not
static boolean is_prime(int n)
{
    if (n <= 1)
        return false;
 
    for(int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
 
// Function to find the count of
// smaller primes on the right
// of each array element
static void countSmallerPrimes(int ar[], int N)
{
    for(int i = 0; i < N; i++)
    {
         
        // Stores the count of
        // smaller primes
        int count = 0;
        for(int j = i + 1; j < N; j++)
        {
             
            // If A[j] <= A[i] and A[j] is prime
            if (ar[j] <= ar[i] && is_prime(ar[j]))
            {
                 
                // Increase count
                count++;
            }
        }
 
        // Print the count for
        // the current element
        System.out.print(count + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int ar[] = { 43, 3, 5, 7, 2, 41 };
    int N = ar.length;
 
    // Function call
    countSmallerPrimes(ar, N);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
 
# Function to check if a
# number is prime or not
def is_prime(n):
     
    if (n <= 1):
        return 0
 
    for i in range(2, n + 1):
        if i * i > n:
            break
         
        if (n % i == 0):
            return 0
             
    return 1
 
# Function to find the count of
# smaller primes on the right
# of each array element
def countSmallerPrimes(ar, N):
 
    for i in range(N):
 
        # Stores the count of
        # smaller primes
        count = 0
        for j in range(i + 1, N):
 
            # If A[j] <= A[i] and A[j] is prime
            if (ar[j] <= ar[i] and is_prime(ar[j])):
 
                # Increase count
                count += 1
 
        # Print the count for
        # the current element
        print(count, end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    ar = [ 43, 3, 5, 7, 2, 41 ]
    N = len(ar)
 
    # Function call
    countSmallerPrimes(ar, N)
 
# This code is contributed by mohit kumar 29

C#

// C# program for
// the above approach
using System;
class GFG{
 
// Function to check if a
// number is prime or not
static bool is_prime(int n)
{
  if (n <= 1)
    return false;
 
  for (int i = 2;
           i * i <= n; i++)
  {
    if (n % i == 0)
      return false;
  }
   
  return true;
}
 
// Function to find the count of
// smaller primes on the right
// of each array element
static void countSmallerPrimes(int[] ar,
                               int N)
{
  for (int i = 0; i < N; i++)
  {
    // Stores the count of
    // smaller primes
    int count = 0;
     
    for (int j = i + 1; j < N; j++)
    {
      // If A[j] <= A[i]
      // and A[j] is prime
      if (ar[j] <= ar[i] &&
          is_prime(ar[j]))
      {
        // Increase count
        count++;
      }
    }
 
    // Print the count for
    // the current element
    Console.Write(count + " ");
  }
}
 
// Driver Code
public static void Main()
{
  int[] ar = {43, 3, 5,
              7, 2, 41};
  int N = ar.Length;
 
  // Function call
  countSmallerPrimes(ar, N);
}
}
 
// This code is contributed by Chitranayal

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to check if a
// number is prime or not
function is_prime(n)
{
    if (n <= 1)
        return false;
 
    for(let i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
 
// Function to find the count of
// smaller primes on the right
// of each array element
function countSmallerPrimes(ar, N)
{
    for(let i = 0; i < N; i++)
    {
         
        // Stores the count of
        // smaller primes
        let count = 0;
        for(let j = i + 1; j < N; j++)
        {
             
            // If A[j] <= A[i] and A[j] is prime
            if (ar[j] <= ar[i] && is_prime(ar[j]))
            {
                 
                // Increase count
                count++;
            }
        }
 
        // Print the count for
        // the current element
        document.write(count + " ");
    }
}
 
// Driver Code
 
    let ar = [ 43, 3, 5, 7, 2, 41 ];
    let N = ar.length;
 
    // Function call
    countSmallerPrimes(ar, N);
 
</script>
Producción

5 1 1 1 0 0 

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es observar que el enfoque anterior se puede optimizar iterando sobre la array de derecha a izquierda y calculando el recuento requerido de números primos para cada elemento de la array utilizando Fenwick Tree . Siga los pasos a continuación para resolver el problema:

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;
 
const int maxn = 1e6 + 5;
int BITree[maxn];
 
// Function to check if a
// number is prime or not
bool is_prime(int n)
{
    if (n <= 1)
        return 0;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return 0;
    return 1;
}
 
// Function to update a Binary Tree
void update_bitree(int BITree[],
                   int index, int value)
{
    while (index <= maxn) {
        BITree[index] += value;
        index += (index & (-index));
    }
}
 
// Function to find the sum of
// all the elements which are
// less than or equal to index
int sum_bitree(int BITree[], int index)
{
    int s = 0;
    while (index > 0) {
        s += BITree[index];
        index -= (index & (-index));
    }
    return s;
}
 
// Function to find the number
// of smaller primes on the right
// for every array element
void countSmallerPrimes(int BITree[],
                        int ar[], int N)
{
    int ans[N];
 
    // Iterate the array in backwards
    for (int i = N - 1; i >= 0; i--) {
 
        // Calculating the required
        // number of primes
        ans[i] = sum_bitree(BITree, ar[i]);
 
        // If current array
        // element is prime
        if (is_prime(ar[i]))
 
            // Update the Fenwick tree
            update_bitree(BITree, ar[i], 1);
    }
    for (int i = 0; i < N; i++)
        cout << ans[i] << " ";
}
 
// Driver Code
int main()
{
 
    int ar[] = { 5, 5, 17, 9, 12,
                 15, 11, 7, 39, 3 };
    int N = sizeof ar / sizeof ar[0];
 
    // Function call
    countSmallerPrimes(BITree, ar, N);
 
    return 0;
}

Java

// Java Program for the
// above approach
//include "bits/stdJava.h"
import java.util.*;
class GFG{
 
static int maxn =
       (int)1e6 + 5;
static int []BITree =
       new int[maxn];
 
// Function to check if a
// number is prime or not
static boolean is_prime(int n)
{
  if (n <= 1)
    return false;
   
  for (int i = 2;
           i * i <= n; i++)
    if (n % i == 0)
      return false;
   
  return true;
}
 
// Function to update a Binary Tree
static void update_bitree(int BITree[],
                          int index,
                          int value)
{
  while (index <= maxn)
  {
    BITree[index] += value;
    index += (index & (-index));
  }
}
 
// Function to find the sum of
// all the elements which are
// less than or equal to index
static int sum_bitree(int BITree[],
                      int index)
{
  int s = 0;
  while (index > 0)
  {
    s += BITree[index];
    index -= (index & (-index));
  }
  return s;
}
 
// Function to find the number
// of smaller primes on the right
// for every array element
static void countSmallerPrimes(int BITree[],
                               int ar[], int N)
{
  int []ans = new int[N];
 
  // Iterate the array in backwards
  for (int i = N - 1; i >= 0; i--)
  {
    // Calculating the required
    // number of primes
    ans[i] = sum_bitree(BITree,
                        ar[i]);
 
    // If current array
    // element is prime
    if (is_prime(ar[i]))
 
      // Update the Fenwick tree
      update_bitree(BITree,
                    ar[i], 1);
  }
   
  for (int i = 0; i < N; i++)
    System.out.print(ans[i] + " ");
}
 
// Driver Code
public static void main(String[] args)
{
  int ar[] = {5, 5, 17, 9, 12,
              15, 11, 7, 39, 3};
  int N = ar.length;
 
  // Function call
  countSmallerPrimes(BITree, ar, N);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the
# above approach
 
# include "bits/stdPython.h"
maxn = int(1e6) + 5
 
BITree = [0] * (maxn)
 
# Function to check if a
# number is prime or not
def is_prime(n):
     
    if (n <= 1):
        return False
         
    i = 2
    while (i * i <= n):
        if (n % i == 0):
            return False
             
        i += 1
 
    return True
 
# Function to update a Binary Tree
def update_bitree(index, value):
     
    while (index <= maxn):
        BITree[index] += value
        index += (index & (-index))
         
# Function to find the sum of
# all the elements which are
# less than or equal to index
def sum_bitree(index):
     
    s = 0
    while (index > 0):
        s += BITree[index]
        index -= (index & (-index))
 
    return s
 
# Function to find the number
# of smaller primes on the right
# for every array element
def countSmallerPrimes(ar, N):
     
    ans = [0] * (N)
    global BITree
     
    # Iterate the array in backwards
    for i in range(N - 1, 0, -1):
         
        # Calculating the required
        # number of primes
        ans[i] = sum_bitree(ar[i])
 
        # If current array
        # element is prime
        if (is_prime(ar[i])):
             
            # Update the Fenwick tree
            update_bitree(ar[i], 1)
             
    ans[0] = 2
    for i in range(N):
        print(ans[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    ar = [ 5, 5, 17, 9, 12,
           15, 11, 7, 39, 3 ]
            
    N = len(ar)
 
    # Function call
    countSmallerPrimes(ar, N)
 
# This code is contributed by Amit Katiyar

C#

// C# Program for the
// above approach
//include "bits/stdJava.h"
using System;
class GFG{
 
static int maxn =
       (int)1e6 + 5;
static int []BITree =
       new int[maxn];
 
// Function to check if a
// number is prime or not
static bool is_prime(int n)
{
  if (n <= 1)
    return false;
   
  for (int i = 2;
           i * i <= n; i++)
    if (n % i == 0)
      return false;
   
  return true;
}
 
// Function to update a Binary Tree
static void update_bitree(int []BITree,
                          int index,
                          int value)
{
  while (index <= maxn)
  {
    BITree[index] += value;
    index += (index & (-index));
  }
}
 
// Function to find the sum of
// all the elements which are
// less than or equal to index
static int sum_bitree(int []BITree,
                      int index)
{
  int s = 0;
  while (index > 0)
  {
    s += BITree[index];
    index -= (index & (-index));
  }
  return s;
}
 
// Function to find the number
// of smaller primes on the right
// for every array element
static void countSmallerPrimes(int []BITree,
                               int []ar, int N)
{
  int []ans = new int[N];
 
  // Iterate the array in backwards
  for (int i = N - 1; i >= 0; i--)
  {
    // Calculating the required
    // number of primes
    ans[i] = sum_bitree(BITree,
                        ar[i]);
 
    // If current array
    // element is prime
    if (is_prime(ar[i]))
 
      // Update the Fenwick tree
      update_bitree(BITree,
                    ar[i], 1);
  }
   
  for (int i = 0; i < N; i++)
    Console.Write(ans[i] + " ");
}
 
// Driver Code
public static void Main(String[] args)
{
  int []ar = {5, 5, 17, 9, 12,
              15, 11, 7, 39, 3};
  int N = ar.Length;
 
  // Function call
  countSmallerPrimes(BITree, ar, N);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
    // Javascript Program for the above approach
     
    let maxn = 1e6 + 5;
        
    let BITree = new Array(maxn);
    BITree.fill(0);
 
    // Function to check if a
    // number is prime or not
    function is_prime(n)
    {
      if (n <= 1)
        return false;
 
      for (let i = 2; i * i <= n; i++)
        if (n % i == 0)
          return false;
 
      return true;
    }
 
    // Function to update a Binary Tree
    function update_bitree(BITree, index, value)
    {
      while (index <= maxn)
      {
        BITree[index] += value;
        index += (index & (-index));
      }
    }
 
    // Function to find the sum of
    // all the elements which are
    // less than or equal to index
    function sum_bitree(BITree, index)
    {
      let s = 0;
      while (index > 0)
      {
        s += BITree[index];
        index -= (index & (-index));
      }
      return s;
    }
 
    // Function to find the number
    // of smaller primes on the right
    // for every array element
    function countSmallerPrimes(BITree, ar, N)
    {
      let ans = new Array(N);
 
      // Iterate the array in backwards
      for (let i = N - 1; i >= 0; i--)
      {
        // Calculating the required
        // number of primes
        ans[i] = sum_bitree(BITree, ar[i]);
 
        // If current array
        // element is prime
        if (is_prime(ar[i]))
 
          // Update the Fenwick tree
          update_bitree(BITree, ar[i], 1);
      }
 
      for (let i = 0; i < N; i++)
        document.write(ans[i] + " ");
    }
     
    let ar = [5, 5, 17, 9, 12, 15, 11, 7, 39, 3];
    let N = ar.length;
 
    // Function call
    countSmallerPrimes(BITree, ar, N);
 
</script>
Producción

2 1 3 2 3 3 2 1 1 0 

Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por dbarnwal888 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 *