Recuento de formas de dividir un número dado en segmentos primos

Dada la string numérica str , la tarea es contar el número de formas en que se puede dividir la string dada, de modo que cada segmento sea un número primo. Dado que la respuesta puede ser grande, devuelve la respuesta módulo 10 9 + 7
Nota : una división que contenga números con ceros a la izquierda no será válida y la string inicial no contiene ceros a la izquierda.
Ejemplos: 

Entrada: str = “3175” 
Salida:
Explicación: 
Hay 3 formas de dividir esta string en números primos que son (31, 7, 5), (3, 17, 5), (317, 5).
Entrada: str = «11373» 
Salida:
Explicación: 
Hay 6 formas de dividir esta string en números primos que son (11, 3, 7, 3), (113, 7, 3), (11, 37, 3) , (11, 3, 73), (113, 73) y (11, 373). 

Enfoque ingenuo: para resolver el problema mencionado anteriormente, el método ingenuo es usar Recursion .  

  • Comience recursivamente desde el índice final de la string dada y considere cada sufijo hasta 6 dígitos (dado que el número primo debe estar en el rango de [1, 10 6 )] y verifique si es un número primo o no.
  • Si el sufijo no contiene un cero inicial y es un número primo, llame recursivamente a la función para contar las formas de la string restante y agregar al recuento total.
  • Cuando el índice llega a 0, llegamos al caso base y devolvemos 1 para considerar las divisiones actuales como un recuento válido.
  • Tome mod de la cuenta en cada iteración y devuelva la cuenta al final.

A continuación se muestra el enfoque de implementación anterior:
 

C++

// C++ implementation to count total
// number of ways to split a
// string to get prime numbers
 
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
 
// Function to check whether a number
// is a prime number or not
bool isPrime(string number)
{
    int num = stoi(number);
    for (int i = 2; i * i <= num; i++)
        if ((num % i) == 0)
            return false;
    return num > 1 ? true : false;
}
 
// Function to find the count
// of ways to split string
// into prime numbers
int countPrimeStrings(
    string& number, int i)
{
 
    // 1 based indexing
    if (i == 0)
        return 1;
    int cnt = 0;
 
    // Consider every suffix up to 6 digits
    for (int j = 1; j <= 6; j++) {
 
        // Number should not have
        // a leading zero and
        // it should be a prime number
        if (i - j >= 0
            && number[i - j] != '0'
            && isPrime(
                   number.substr(i - j, j))) {
            cnt
                += countPrimeStrings(
                    number,
                    i - j);
 
            cnt %= MOD;
        }
    }
 
    // Return the final result
    return cnt;
}
 
// Driver code
int main()
{
    string s1 = "3175";
 
    int l = s1.length();
    cout << countPrimeStrings(s1, l);
 
    return 0;
}

Java

// Java implementation to count total
// number of ways to split a string
// to get prime numbers
import java.util.*;
 
class GFG{
     
static final int MOD =1000000007;
 
// Function to check whether a number
// is a prime number or not
static boolean isPrime(String number)
{
    int num = Integer.valueOf(number);
     
    for(int i = 2; i * i <= num; i++)
    {
       if ((num % i) == 0)
           return false;
    }
    return num > 1 ? true : false;
}
 
// Function to find the count
// of ways to split String
// into prime numbers
static int countPrimeStrings(String number,
                                     int i)
{
 
    // 1 based indexing
    if (i == 0)
        return 1;
         
    int cnt = 0;
 
    // Consider every suffix up to 6 digits
    for(int j = 1; j <= 6; j++)
    {
        
       // Number should not have
       // a leading zero and it
       // should be a prime number
       if (i - j >= 0 &&
           number.charAt(i - j) != '0' &&
           isPrime(number.substring(i - j, i)))
       {
           cnt += countPrimeStrings(number,
                                    i - j);
           cnt %= MOD;
       }
    }
     
    // Return the final result
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
    String s1 = "3175";
    int l = s1.length();
     
    System.out.print(countPrimeStrings(s1, l));
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python3 implementation to
# count total number of ways
# to split a string to get
# prime numbers
MOD = 1000000007
 
# Function to check whether
# a number is a prime number
# or not
def isPrime(number):
 
    num = int(number)
    i = 2
     
    while i * i <= num:
        if ((num % i) == 0):
            return False
        i += 1
         
    if num > 1:
      return True
    else:
      return False
 
# Function to find the count
# of ways to split string
# into prime numbers
def countPrimeStrings(number, i):
 
    # 1 based indexing
    if (i == 0):
        return 1
    cnt = 0
 
    # Consider every suffix
    # up to 6 digits
    for j in range(1, 7):
 
        # Number should not have
        # a leading zero and
        # it should be a prime number
        if (i - j >= 0 and
            number[i - j] != '0' and
            isPrime(number[i - j : i])):
            cnt += countPrimeStrings(number,
                                     i - j)
            cnt %= MOD
         
    # Return the final result
    return cnt
 
# Driver code
if __name__ == "__main__":
   
    s1 = "3175"
    l = len(s1)
    print (countPrimeStrings(s1, l))
 
# This code is contributed by Chitranayal

C#

// C# implementation to count total
// number of ways to split a string
// to get prime numbers
using System;
class GFG{
     
static readonly int MOD =1000000007;
 
// Function to check whether a number
// is a prime number or not
static bool isPrime(String number)
{
    int num = Int32.Parse(number);
     
    for(int i = 2; i * i <= num; i++)
    {
        if ((num % i) == 0)
            return false;
    }
    return num > 1 ? true : false;
}
 
// Function to find the count
// of ways to split String
// into prime numbers
static int countPrimeStrings(String number,
                                     int i)
{
 
    // 1 based indexing
    if (i == 0)
        return 1;
         
    int cnt = 0;
 
    // Consider every suffix up to 6 digits
    for(int j = 1; j <= 6; j++)
    {
         
        // Number should not have
        // a leading zero and it
        // should be a prime number
        if (i - j >= 0 &&
            number[i - j] != '0' &&
            isPrime(number.Substring(i - j, j)))
        {
            cnt += countPrimeStrings(number,
                                     i - j);
            cnt %= MOD;
        }
    }
     
    // Return the readonly result
    return cnt;
}
 
// Driver code
public static void Main(String[] args)
{
    String s1 = "3175";
    int l = s1.Length;
     
    Console.Write(countPrimeStrings(s1, l));
}
}
 
// This code is contributed by sapnasingh4991

Javascript

<script>
// Javascript implementation to count total
// number of ways to split a string
// to get prime numbers
 
let MOD =1000000007;
// Function to check whether a number
// is a prime number or not
function isPrime(number)
{
    let num = parseInt(number);
      
    for(let i = 2; i * i <= num; i++)
    {
       if ((num % i) == 0)
           return false;
    }
    return num > 1 ? true : false;
}
 
// Function to find the count
// of ways to split String
// into prime numbers
function countPrimeStrings(number,i)
{
    // 1 based indexing
    if (i == 0)
        return 1;
          
    let cnt = 0;
  
    // Consider every suffix up to 6 digits
    for(let j = 1; j <= 6; j++)
    {
         
       // Number should not have
       // a leading zero and it
       // should be a prime number
       if (i - j >= 0 &&
           number[i - j] != '0' &&
           isPrime(number.substring(i - j, i)))
       {
           cnt += countPrimeStrings(number,
                                    i - j);
           cnt %= MOD;
       }
    }
      
    // Return the final result
    return cnt;
}
 
// Driver code
let s1 = "3175";
let l = s1.length;
document.write(countPrimeStrings(s1, l));
 
 
 
// This code is contributed by avanitrachhadiya2155
</script>
Producción: 

3

 

Complejidad de tiempo: O(N 2 )  
Espacio auxiliar: O(N)
Enfoque eficiente: Para optimizar el método anterior, la idea principal es usar la técnica de memorización para reducir la complejidad de tiempo de la solución recursiva discutida anteriormente. Consideremos una tabla dp[] que almacena en cada índice dp[i] , las formas de dividir los primeros i dígitos de la string str . La complejidad para comprobar si un número es primo o no puede reducirse aún más utilizando la criba de Eratóstenes .
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation to count total
// number of ways to split a
// string to get prime numbers
 
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
bool sieve[1000000];
 
// Function to build sieve
void buildSieve()
{
    for (auto& i : sieve)
        i = true;
 
    sieve[0] = false;
    sieve[1] = false;
 
    for (int p = 2; p * p <= 1000000;
         p++) {
 
        // If p is a prime
        if (sieve[p] == true) {
 
            // Update all multiples
            // of p as non prime
 
            for (int i = p * p; i <= 1000000;
                 i += p)
                sieve[i] = false;
        }
    }
}
 
// Function to check whether a number
// is a prime number or not
bool isPrime(string number)
{
    int num = stoi(number);
    return sieve[num];
}
 
// Function to find the count
// of ways to split string
// into prime numbers
int rec(string& number, int i,
        vector<int>& dp)
{
    if (dp[i] != -1)
        return dp[i];
 
    int cnt = 0;
 
    for (int j = 1; j <= 6; j++) {
 
        // Number should not have a
        // leading zero and it
        // should be a prime number
        if (i - j >= 0
            && number[i - j] != '0'
            && isPrime(
                   number.substr(i - j, j))) {
 
            cnt += rec(
                number, i - j, dp);
            cnt %= MOD;
        }
    }
    return dp[i] = cnt;
}
 
// Function to count the
// number of prime strings
int countPrimeStrings(string& number)
{
    int n = number.length();
    vector<int> dp(n + 1, -1);
    dp[0] = 1;
    return rec(number, n, dp);
}
 
// Driver code
int main()
{
    buildSieve();
 
    string s1 = "3175";
 
    cout << countPrimeStrings(s1) << "\n";
 
    return 0;
}

Java

// Java implementation to count total
// number of ways to split a String
// to get prime numbers
import java.util.*;
 
class GFG{
     
static int MOD = 1000000007;
static boolean []sieve = new boolean[1000000];
 
// Function to build sieve
static void buildSieve()
{
    Arrays.fill(sieve, true);
 
    sieve[0] = false;
    sieve[1] = false;
 
    for(int p = 2; p * p <= 1000000; p++)
    {
 
       // If p is a prime
       if (sieve[p] == true)
       {
 
           // Update all multiples
           // of p as non prime
           for(int i = p * p; i < 1000000;
                   i += p)
              sieve[i] = false;
       }
    }
}
 
// Function to check whether a number
// is a prime number or not
static boolean isPrime(String number)
{
    int num = Integer.valueOf(number);
    return sieve[num];
}
 
// Function to find the count
// of ways to split String
// into prime numbers
static int rec(String number, int i,
                              int []dp)
{
    if (dp[i] != -1)
        return dp[i];
    int cnt = 0;
 
    for(int j = 1; j <= 6; j++)
    {
        
       // Number should not have a
       // leading zero and it
       // should be a prime number
       if (i - j >= 0 &&
           number.charAt(i - j) != '0' &&
           isPrime(number.substring(i - j, i)))
       {
           cnt += rec(number, i - j, dp);
           cnt %= MOD;
       }
    }
    return dp[i] = cnt;
}
 
// Function to count the
// number of prime Strings
static int countPrimeStrings(String number)
{
    int n = number.length();
    int []dp = new int[n + 1];
     
    Arrays.fill(dp, -1);
    dp[0] = 1;
 
    return rec(number, n, dp);
}
 
// Driver code
public static void main(String[] args)
{
    buildSieve();
 
    String s1 = "3175";
 
    System.out.print(countPrimeStrings(s1) + "\n");
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation to count total
# number of ways to split a String
# to get prime numbers
MOD = 1000000007
sieve = [0]*(1000000)
  
# Function to build sieve
def buildSieve():
    for i in range(len(sieve)):
        sieve[i] = True
      
    sieve[0] = False
    sieve[1] = False
     
    p = 2
    while p*p <= 1000000:
        # If p is a prime
        if sieve[p] == True:
            # Update all multiples
            # of p as non prime
            for i in range(p*p, 1000000, p):
                sieve[i] = False
        p+=1
       
  
# Function to check whether a number
# is a prime number or not
def isPrime(number):
    num = int(number)
    return sieve[num]
  
# Function to find the count
# of ways to split String
# into prime numbers
def rec(number,i,dp):
    if dp[i] != -1:
        return dp[i]
    cnt = 0
   
    for j in range(1, 7):
       # Number should not have a
       # leading zero and it
       # should be a prime number
       if (i - j) >= 0 and number[i - j] != '0' and isPrime(number[i - j: i]):
           cnt += rec(number, i - j, dp)
           cnt %= MOD
    dp[i] = cnt
    return dp[i]
  
# Function to count the
# number of prime Strings
def countPrimeStrings(number):
    n = len(number)
    dp = [0]*(n + 1)
      
    for i in range(n + 1):
        dp[i] = -1
      
    dp[0] = 1
   
    return rec(number, n, dp)
 
# Driver code
buildSieve()
s1 = "3175"
print(countPrimeStrings(s1))
 
# This code is contributed by suresh07.

C#

// C# implementation to count total
// number of ways to split a String
// to get prime numbers
using System;
 
class GFG{
     
static int MOD = 1000000007;
static bool []sieve = new bool[1000000];
 
// Function to build sieve
static void buildSieve()
{
    for(int j = 0; j < sieve.Length; j++)
       sieve[j] = true;
 
    sieve[0] = false;
    sieve[1] = false;
 
    for(int p = 2; p * p <= 1000000; p++)
    {
        
       // If p is a prime
       if (sieve[p] == true)
       {
            
           // Update all multiples
           // of p as non prime
           for(int i = p * p; i < 1000000;
                   i += p)
              sieve[i] = false;
       }
    }
}
 
// Function to check whether a number
// is a prime number or not
static bool isPrime(String number)
{
    int num = Int32.Parse(number);
    return sieve[num];
}
 
// Function to find the count
// of ways to split String
// into prime numbers
static int rec(String number, int i,
                              int []dp)
{
    if (dp[i] != -1)
        return dp[i];
    int cnt = 0;
 
    for(int j = 1; j <= 6; j++)
    {
        
       // Number should not have a
       // leading zero and it
       // should be a prime number
       if (i - j >= 0 &&
           number[i - j] != '0' &&
           isPrime(number.Substring(i - j, j)))
       {
           cnt += rec(number, i - j, dp);
           cnt %= MOD;
       }
    }
    return dp[i] = cnt;
}
 
// Function to count the
// number of prime Strings
static int countPrimeStrings(String number)
{
    int n = number.Length;
    int []dp = new int[n + 1];
     
    for(int j = 0; j < dp.Length; j++)
       dp[j] = -1;
    dp[0] = 1;
 
    return rec(number, n, dp);
}
 
// Driver code
public static void Main(String[] args)
{
    buildSieve();
 
    String s1 = "3175";
 
    Console.Write(countPrimeStrings(s1) + "\n");
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript implementation to count total
// number of ways to split a String
// to get prime numbers
let MOD = 1000000007;
let sieve = new Array(1000000);
 
// Function to build sieve
function buildSieve()
{
    for(let i = 0; i < sieve.length; i++)
    {
        sieve[i] = true;
    }
     
    sieve[0] = false;
    sieve[1] = false;
  
    for(let p = 2; p * p <= 1000000; p++)
    {
  
       // If p is a prime
       if (sieve[p] == true)
       {
  
           // Update all multiples
           // of p as non prime
           for(let i = p * p; i < 1000000;
                   i += p)
              sieve[i] = false;
       }
    }
}
 
// Function to check whether a number
// is a prime number or not
function isPrime(number)
{
    let num = parseInt(number);
    return sieve[num];
}
 
// Function to find the count
// of ways to split String
// into prime numbers
function rec(number,i,dp)
{
    if (dp[i] != -1)
        return dp[i];
    let cnt = 0;
  
    for(let j = 1; j <= 6; j++)
    {
         
       // Number should not have a
       // leading zero and it
       // should be a prime number
       if (i - j >= 0 &&
           number[i - j] != '0' &&
           isPrime(number.substring(i - j, i)))
       {
           cnt += rec(number, i - j, dp);
           cnt %= MOD;
       }
    }
    return dp[i] = cnt;
}
 
// Function to count the
// number of prime Strings
function countPrimeStrings(number)
{
    let n = number.length;
    let dp = new Array(n + 1);
     
    for(let i = 0; i < (n + 1); i++)
    {
        dp[i] = -1;
    }
     
    dp[0] = 1;
  
    return rec(number, n, dp);
}
 
// Driver code
buildSieve();
let s1 = "3175";
document.write(countPrimeStrings(s1) + "<br>");
 
// This code is contributed by rag2127
</script>
Producción: 

3

 

Complejidad de tiempo: O(N + N*log(log(N)))  
Espacio auxiliar: O(N)

Publicación traducida automáticamente

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