Cuente los números primos menores que el número formado al reemplazar los dígitos de la suma de la array con el número primo hasta el dígito

Dada una array arr[] de tamaño N que solo tiene elementos positivos, la tarea es encontrar el número de primos menor que el número formado después de seguir las siguientes operaciones:

• Agregue todos los elementos de la array dada, diga suma
• Reemplace cada dígito de la suma con el número total de números primos que se encuentran entre 0 y ese dígito.

Ejemplos:

Entrada: N = 5, arr[] = {7, 12, 9, 27, 1}
Salida: 11
Explicación: La suma de todos los elementos es 56. 
Los números primos entre [0, 5] y [0, 6] son ​​3 , que son (2, 3, 5). 
Entonces, el nuevo número se convierte en 33. 
Ahora los números primos totales entre [0, 33] son ​​11. 
Así que la respuesta final será 11.

Entrada: N = 4, arr[] = {1, 2, 3, 4}
Salida: 0

Algoritmo: Este es un problema simple basado en la implementación. La idea es realizar las operaciones una por una como se mencionó y finalmente contar el número de números primos.

Siga los pasos que se mencionan a continuación para resolver el problema.

• Encuentre la suma total de la array dada.
• Convierta la suma en una string, digamos S .
• Itere sobre la string y reemplace cada carácter con el número de números primos entre 0 y ese carácter.
• Convierta la string recién formada en un entero Y. 
• Cuente el número total de números primos entre 0 y Y y devuélvalo.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check prime
bool checkPrime(int numberToCheck)
{
    if (numberToCheck == 1
        || numberToCheck == 0) {
        return false;
    }
    for (int i = 2; i * i <= numberToCheck;
         i++) {
        if (numberToCheck % i == 0) {
            return false;
        }
    }
    return true;
}
 
// Function to calculate total prime numbers
// between 0 to r
int totalprime(int r)
{
    // Count the number of primes
    int count = 0;
    for (int i = r; i >= 0; i--) {
        count += checkPrime(i);
    }
    return count;
}
 
// Function to find required count of primes
int findNum(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
 
    // Converting sum to string
    string s = to_string(sum);
 
    // Calculating total prime numbers:
    for (int i = 0; i < s.length(); i++) {
        s[i] = totalprime(s[i] - '0') + '0';
    }
 
    // Converting newly formed string s
    // to integer.
    int y = stoi(s);
    return totalprime(y);
}
 
// Driver's code
int main()
{
    int arr[] = { 7, 12, 9, 27, 1 };
    int N = 5, sum = 0;
 
    // Function call
    cout << findNum(arr, N);
    return 0;
}

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG
{
   
  // Function to check prime
  public static boolean checkPrime(int numberToCheck)
  {
    if (numberToCheck == 1 || numberToCheck == 0) {
      return false;
    }
    for (int i = 2; i * i <= numberToCheck; i++) {
      if (numberToCheck % i == 0) {
        return false;
      }
    }
    return true;
  }
 
  // Function to calculate total prime numbers
  // between 0 to r
  public static int totalprime(int r)
  {
     
    // Count the number of primes
    int count = 0;
    for (int i = r; i >= 0; i--) {
      if (checkPrime(i) == true)
        count += 1;
    }
    return count;
  }
 
  // Function to find required count of primes
  public static int findNum(int arr[], int n)
  {
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += arr[i];
    }
 
    // Converting sum to string
    StringBuilder s
      = new StringBuilder(Integer.toString(sum));
 
    // Calculating total prime numbers:
    for (int i = 0; i < s.length(); i++) {
      s.setCharAt(i,
                  (char)(totalprime(s.charAt(i) - '0')
                         + '0'));
    }
 
    // Converting newly formed string s
    // to integer.
    int y = Integer.parseInt(s.toString());
    return totalprime(y);
  }
  public static void main(String[] args)
  {
    int arr[] = { 7, 12, 9, 27, 1 };
    int N = 5, sum = 0;
 
    // Function call
    System.out.print(findNum(arr, N));
  }
}
 
// This code is contributed by Rohit Pradhan

# Python code to implement the approach
 
# Function to check prime
def checkPrime(numberToCheck):
    if (numberToCheck == 1 or numberToCheck == 0):
        return False
    i = 2
    while(i * i <= numberToCheck):
        if (numberToCheck % i == 0):
            return False
        i += 1
    return True
 
# Function to calculate total prime numbers
# between 0 to r
def totalprime(r):
   
    # Count the number of primes
    count = 0
    for i in range(r,-1,-1):
        count += checkPrime(i)
    return count
 
# Function to find required count of primes
def findNum(arr, n):
    sum = 0
    for i in range(n):
        sum += arr[i]
 
    # Converting sum to string
    s = str(sum)
 
    # Calculating total prime numbers:
    for i in range(len(s)):
        s = s.replace(s[i],chr(totalprime(ord(s[i]) - ord('0')) + ord('0')))
 
    # Converting newly formed string s
    # to integer.
    y = int(s)
    return totalprime(y)
 
# Driver's code
arr = [ 7, 12, 9, 27, 1 ]
N,sum = 5,0
 
# Function call
print(findNum(arr, N))
 
# This code is contributed by shinjanpatra

// C# code to implement the approach
using System;
 
public class GFG
{
   
  // Function to check prime
  public static bool checkPrime(int numberToCheck)
  {
    if (numberToCheck == 1 || numberToCheck == 0) {
      return false;
    }
    for (int i = 2; i * i <= numberToCheck; i++) {
      if (numberToCheck % i == 0) {
        return false;
      }
    }
    return true;
  }
 
  // Function to calculate total prime numbers
  // between 0 to r
  public static int totalprime(int r)
  {
     
    // Count the number of primes
    int count = 0;
    for (int i = r; i >= 0; i--) {
      if (checkPrime(i) == true)
        count += 1;
    }
    return count;
  }
 
  // Function to find required count of primes
  public static int findNum(int []arr, int n)
  {
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += arr[i];
    }
 
    // Converting sum to string
    String s
      = Convert. ToString(sum) ;
 
    // Calculating total prime numbers:
    for (int i = 0; i < s.Length; i++) {
        s = s.Substring(0,i)+(char)(totalprime(s[i] - '0')
                         + '0')+s.Substring(i+1);
    }
 
    // Converting newly formed string s
    // to integer.
    int y = Int32.Parse(s);
    return totalprime(y);
  }
  public static void Main(String[] args)
  {
    int []arr = { 7, 12, 9, 27, 1 };
    int N = 5, sum = 0;
 
    // Function call
    Console.Write(findNum(arr, N));
  }
}
 
// This code contributed by shikhasingrajput

//JavaScript code to implement the approach
 
// Function to check prime
function checkPrime(numberToCheck)
{
    if (numberToCheck == 1 || numberToCheck == 0)
        return false;
    var i = 2;
    while(i * i <= numberToCheck)
    {
        if (numberToCheck % i == 0)
            return false;
        i += 1;
    }
    return true;
}
 
// Function to calculate total prime numbers
// between 0 to r
function totalprime(r)
{
   
    // Count the number of primes
    var count = 0;
    for (var i = r; i > -1; i--)
        count += checkPrime(i);
    return count;
}
 
 
// Function to find required count of primes
function findNum(arr, n)
{
    var sum = 0;
    for (var i = 0; i < n; i++)
        sum += arr[i];
 
    // Converting sum to string
    var s = sum.toString().split("");
 
    // Calculating total prime numbers:
    for (var i = 0; i < s.length; i++)
        s[i] = totalprime(Number(s[i]));
 
    // Converting newly formed string s
    // to integer.
    var y = Number(s.join(""));
    return totalprime(y);
}
 
// Driver's code
var arr = [ 7, 12, 9, 27, 1 ];
var N = 5;
 
// Function call
console.log(findNum(arr, N));
 
// This code is contributed by phasing17

11

Complejidad del tiempo:O(N)
Espacio Auxiliar:O(1)