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.
- Caso base: si el índice alcanza la longitud de la string , convierta la string en un número entero y verifique si el número formado es primo o no y, si es primo , luego agregue el número en HashSet Primes .
- Llame a la función uniquePrimeNums para elegir, ya sea tomando el carácter, es decir, uniquePrimeNums(number, ans + number.charAt(index), index + 1) o dejando el carácter, es decir, uniquePrimeNums(number, ans, index + 1) .
- 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