Conteo de números primos únicos formados al eliminar dígitos de un número dado

Posted on by Rudeus Greyrat

Dado un número N, la tarea es contar la cantidad de números primos únicos que se pueden formar al eliminar cero o más dígitos del número dado.

Ejemplos:

Entrada: N = 132
Salida: 3
Explicación: 
Los números primos totales formados al eliminar cero o más dígitos del número dado 132 son 3, es decir, [3, 2, 13]. 

Entrada: N = 2222
Salida: 1

Enfoque : Este problema se puede resolver usando recursividad ya que para cada dígito hay dos opciones, ya sea incluyendo el dígito o no incluyendo el dígito. Para cada elección, verifica si el número formado es un número primo o no . Siga los pasos a continuación para resolver este problema:

  • Inicialice un HashSet, digamos Primes, para almacenar los números primos únicos .
  • Declare una función, digamos, uniquePrimeNums(number, ans, index) , pasando la string numérica N, ans como string vacía y el índice 0 como parámetros.
  • Después de completar los pasos anteriores, imprima el tamaño de HashSet Primes como la respuesta requerida.

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 whether the number
// is prime or not
bool checkprime(int n)
{
    // If n is 1
    if (n == 1) {
        return false;
    }
 
    // If n is 2 or 3
    if (n == 2 || n == 3) {
        return true;
    }
 
    // If n is multiple of 2, 3 or 6
    else if (n % 2 == 0 || n % 3 == 0
             || n % 6 == 0) {
        return false;
    }
 
    // Traversing till sqrt(n)
    for (int i = 6; i * i <= n; i += 6) {
        if (n % (i - 1) == 0
            || n % (i + 1) == 0) {
            return false;
        }
    }
    return true;
}
 
// To store the unique prime numbers
set<int> Primes;
 
// Function to Count the total number
// of unique prime number formed by
// deleting zero or more digits of the
// given number
void uniquePrimeNums(string number, string ans, int index)
{
    // Base Case
    if (index == number.length()) {
 
        if (ans.length() != 0)
 
            // Check whether the number is
            // prime or not
            if (checkprime(stoi(ans))) {
 
                // Adding to the HashSet
                Primes.insert(stoi(ans));
            }
 
        return;
    }
 
    // Recursive call by taking the character
    // at index
    uniquePrimeNums(number,
                    ans + number[index],
                    index + 1);
 
    // Recursive call by not taking the
    // character
    uniquePrimeNums(number, ans, index + 1);
}
     
int main()
{
    // Given Input
    int number = 132;
 
    // Function Call
    uniquePrimeNums("" + to_string(number), "", 0);
    cout << Primes.size();
 
    return 0;
}
 
// This code is contributed by divyeshrabadiya07.

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
public class GFG {
 
    // Function to check whether the number
    // is prime or not
    static boolean checkprime(int n)
    {
        // If n is 1
        if (n == 1) {
            return false;
        }
 
        // If n is 2 or 3
        if (n == 2 || n == 3) {
            return true;
        }
 
        // If n is multiple of 2, 3 or 6
        else if (n % 2 == 0 || n % 3 == 0
                 || n % 6 == 0) {
            return false;
        }
 
        // Traversing till sqrt(n)
        for (int i = 6; i * i <= n; i += 6) {
            if (n % (i - 1) == 0
                || n % (i + 1) == 0) {
                return false;
            }
        }
        return true;
    }
 
    // To store the unique prime numbers
    static HashSet<Integer> Primes
        = new HashSet<>();
 
    // Function to Count the total number
    // of unique prime number formed by
    // deleting zero or more digits of the
    // given number
    static void uniquePrimeNums(
        String number, String ans, int index)
    {
        // Base Case
        if (index == number.length()) {
 
            if (ans.length() != 0)
 
                // Check whether the number is
                // prime or not
                if (checkprime(Integer.parseInt(ans))) {
 
                    // Adding to the HashSet
                    Primes.add(Integer.parseInt(ans));
                }
 
            return;
        }
 
        // Recursive call by taking the character
        // at index
        uniquePrimeNums(number,
                        ans + number.charAt(index),
                        index + 1);
 
        // Recursive call by not taking the
        // character
        uniquePrimeNums(number, ans, index + 1);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given Input
        int number = 132;
 
        // Function Call
        uniquePrimeNums("" + number, "", 0);
        System.out.println(Primes.size());
    }
}

Python3

# Python3 program for the above approach
import math
 
# Function to check whether the number
# is prime or not
def checkprime(n):
 
    # If n is 1
    if (n == 1):
        return False
 
    # If n is 2 or 3
    if (n == 2 or n == 3):
        return True
 
    # If n is multiple of 2, 3 or 6
    elif (n % 2 == 0 or n % 3 == 0 or
          n % 6 == 0):
        return False
 
    # Traversing till sqrt(n)
    k = int(math.sqrt(n))
    for i in range(6, k+1, 6):
        if (n % (i - 1) == 0 or n % (i + 1) == 0):
            return False
             
    return True
   
# Function to Count the total number
# of unique prime number formed by
# deleting zero or more digits of the
# given number
def uniquePrimeNums(number, ans, index):
   
    # Base Case
    length = len(list(number))
     
    if (index == length):
        if (len(ans) != 0):
             
            # Check whether the number is
            # prime or not
            if (checkprime(int(ans))):
                 
                # Adding to the HashSet
                Primes.add(int(ans))
        return
       
    # Recursive call by taking the character
    # at index
    uniquePrimeNums(number, ans + number[index],
                          index + 1)
     
    # Recursive call by not taking the
    # character
    uniquePrimeNums(number, ans, index + 1)
    return
 
# To store the unique prime numbers
Primes = set()
 
# Driver code
if __name__ == '__main__':
   
    # Given Input
    number = 132
     
    # Function Call
    uniquePrimeNums(str(number), "", 0)
    print(len(Primes))
 
# This code is contributed by MuskanKalra1

C#

using System;
using System.Collections.Generic;
public class GFG {
    static bool checkprime(int n)
    {
        // If n is 1
        if (n == 1) {
            return false;
        }
 
        // If n is 2 or 3
        if (n == 2 || n == 3) {
            return true;
        }
 
        // If n is multiple of 2, 3 or 6
        else if (n % 2 == 0 || n % 3 == 0 || n % 6 == 0) {
            return false;
        }
 
        // Traversing till sqrt(n)
        for (int i = 6; i * i <= n; i += 6) {
            if (n % (i - 1) == 0 || n % (i + 1) == 0) {
                return false;
            }
        }
        return true;
    }
 
    // To store the unique prime numbers
    static HashSet<int> Primes = new HashSet<int>();
 
    // Function to Count the total number
    // of unique prime number formed by
    // deleting zero or more digits of the
    // given number
    static void uniquePrimeNums(String number, String ans,
                                int index)
    {
        // Base Case
        if (index == number.Length) {
 
            if (ans.Length != 0)
 
                // Check whether the number is
                // prime or not
                if (checkprime(int.Parse(ans))) {
 
                    // Adding to the HashSet
                    Primes.Add(int.Parse(ans));
                }
 
            return;
        }
 
        // Recursive call by taking the character
        // at index
        uniquePrimeNums(number, ans + number[index],
                        index + 1);
 
        // Recursive call by not taking the
        // character
        uniquePrimeNums(number, ans, index + 1);
    }
 
    // Driver Code
    static public void Main()
    {
        int number = 132;
 
        // Function Call
        uniquePrimeNums("" + number, "", 0);
        Console.WriteLine(Primes.Count);
    }
}
 
// This code is contributed by maddler.

Javascript

<script>
 
// JavaScript implementation of
// the above approach
 
    // Function to check whether the number
    // is prime or not
    function checkprime(n)
    {
        // If n is 1
        if (n == 1) {
            return false;
        }
 
        // If n is 2 or 3
        if (n == 2 || n == 3) {
            return true;
        }
 
        // If n is multiple of 2, 3 or 6
        else if (n % 2 == 0 || n % 3 == 0
                 || n % 6 == 0) {
            return false;
        }
 
        // Traversing till sqrt(n)
        for (let i = 6; i * i <= n; i += 6) {
            if (n % (i - 1) == 0
                || n % (i + 1) == 0) {
                return false;
            }
        }
        return true;
    }
 
    // To store the unique prime numbers
    var Primes
        = new Set();
 
    // Function to Count the total number
    // of unique prime number formed by
    // deleting zero or more digits of the
    // given number
    function uniquePrimeNums(
        number, ans, index)
    {
        // Base Case
        if (index == number.length) {
 
            if (ans.length != 0)
 
                // Check whether the number is
                // prime or not
                if (checkprime(parseInt(ans))) {
 
                    // Adding to the HashSet
                    Primes.add(parseInt(ans));
                }
 
            return;
        }
 
        // Recursive call by taking the character
        // at index
        uniquePrimeNums(number,
                        ans + number[index],
                        index + 1);
 
        // Recursive call by not taking the
        // character
        uniquePrimeNums(number, ans, index + 1);
    }
 
// Driver Code
 
    // Given Input
        let number = 132;
 
        // Function Call
        uniquePrimeNums("" + number, "", 0);
        document.write(Primes.size);
 
</script>
Producción

3

Complejidad de tiempo: O(2 N * sqrt(N))
Espacio auxiliar: O(2 N )

Publicación traducida automáticamente

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