Dada una string str que representa un número grande, la tarea es encontrar el número mínimo de segmentos que la string dada se puede dividir de modo que cada segmento sea un número primo en el rango de 1 a 10 6 .
Ejemplos:
Entrada: str = “13499315”
Salida: 3
Explicación:
El número se puede segmentar como [13499, 31, 5]Entrada: str = “43”
Salida: 1
Explicación:
El número se puede segmentar como [43]
Enfoque ingenuo: la idea es considerar cada prefijo hasta 6 dígitos (dado que se da que los números primos son menores que 10 6 ) y verificar si es un número primo o no. Si el prefijo es un número primo, llame recursivamente a la función para verificar la string restante. Si se devuelve un número no negativo, entonces se considera como un arreglo posible. Si ninguna de las combinaciones posibles devuelve un número positivo, entonces se imprime -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <iostream>
#include <string>
using namespace std;
// Function to check whether a string
// is a prime number or not
bool checkPrime(string number)
{
int num = stoi(number);
for (int i = 2; i * i <= num; i++)
if ((num % i) == 0)
return false;
return true;
}
// A recursive function to find the minimum
// number of segments the given string can
// be divided such that every segment is a prime
int splitIntoPrimes(string number)
{
// If the number is null
if (number.length() == 0)
return 0;
// checkPrime function is called to check if
// the number is a prime or not.
if (number.length() <= 6 and checkPrime(number))
return 1;
else {
int numLen = number.length();
// A very large number denoting maximum
int ans = 1000000;
// Consider a minimum of 6 and length
// since the primes are less than 10 ^ 6
for (int i = 1; i <= 6 && i <= numLen; i++) {
if (checkPrime(number.substr(0, i))) {
// Recursively call the function
// to check for the remaining string
int val = splitIntoPrimes(number.substr(i));
if (val != -1) {
// Evaluating minimum splits
// into Primes for the suffix
ans = min(ans, 1 + val);
}
}
}
// Checks if no combination found
if (ans == 1000000)
return -1;
return ans;
}
}
// Driver code
int main()
{
cout << splitIntoPrimes("13499315") << "\n";
cout << splitIntoPrimes("43") << "\n";
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
// Function to check whether a String
// is a prime number or not
static boolean checkPrime(String number)
{
int num = Integer.valueOf(number);
for (int i = 2; i * i <= num; i++)
if ((num % i) == 0)
return false;
return true;
}
// A recursive function to find the minimum
// number of segments the given String can
// be divided such that every segment is a prime
static int splitIntoPrimes(String number)
{
// If the number is null
if (number.length() == 0)
return 0;
// checkPrime function is called to check if
// the number is a prime or not.
if (number.length() <= 6 && checkPrime(number))
return 1;
else {
int numLen = number.length();
// A very large number denoting maximum
int ans = 1000000;
// Consider a minimum of 6 and length
// since the primes are less than 10 ^ 6
for (int i = 1; i <= 6 && i <= numLen; i++) {
if (checkPrime(number.substring(0, i))) {
// Recursively call the function
// to check for the remaining String
int val = splitIntoPrimes(number.substring(i));
if (val != -1) {
// Evaluating minimum splits
// into Primes for the suffix
ans = Math.min(ans, 1 + val);
}
}
}
// Checks if no combination found
if (ans == 1000000)
return -1;
return ans;
}
}
// Driver code
public static void main(String[] args)
{
System.out.print(splitIntoPrimes("13499315")+ "\n");
System.out.print(splitIntoPrimes("43")+ "\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach
# Function to check whether a string
# is a prime number or not
def checkPrime(number) :
num = int(number)
for i in range(2, int(num**0.5)) :
if((num % i) == 0) :
return False
return True
# A recursive function to find the minimum
# number of segments the given string can
# be divided such that every segment is a prime
def splitIntoPrimes(number) :
# If the number is null
if( number == '' ) :
return 0
# checkPrime function is called to check if
# the number is a prime or not.
if( len(number)<= 6 and checkPrime(number) ) :
return 1
else :
numLen = len(number)
# A very large number denoting maximum
ans = 1000000
# Consider a minimum of 6 and length
# since the primes are less than 10 ^ 6
for i in range( 1, (min( 6, numLen ) + 1) ) :
if( checkPrime( number[:i] ) ) :
# Recursively call the function
# to check for the remaining string
val = splitIntoPrimes( number[i:] )
if(val != -1) :
# Evaluating minimum splits
# into Primes for the suffix
ans = min(ans, 1 + val)
# Checks if no combination found
if( ans == 1000000 ) :
return -1
return ans
# Driver code
print(splitIntoPrimes("13499315"))
print(splitIntoPrimes("43"))
C#
// C# implementation of the above approach
using System;
class GFG{
// Function to check whether a String
// is a prime number or not
static bool checkPrime(String number)
{
int num = Int32.Parse(number);
for (int i = 2; i * i <= num; i++)
if ((num % i) == 0)
return false;
return true;
}
// A recursive function to find the minimum
// number of segments the given String can
// be divided such that every segment is a prime
static int splitIntoPrimes(String number)
{
// If the number is null
if (number.Length == 0)
return 0;
// checkPrime function is called to check if
// the number is a prime or not.
if (number.Length <= 6 && checkPrime(number))
return 1;
else {
int numLen = number.Length;
// A very large number denoting maximum
int ans = 1000000;
// Consider a minimum of 6 and length
// since the primes are less than 10 ^ 6
for (int i = 1; i <= 6 && i <= numLen; i++) {
if (checkPrime(number.Substring(0, i))) {
// Recursively call the function
// to check for the remaining String
int val = splitIntoPrimes(number.Substring(i));
if (val != -1) {
// Evaluating minimum splits
// into Primes for the suffix
ans = Math.Min(ans, 1 + val);
}
}
}
// Checks if no combination found
if (ans == 1000000)
return -1;
return ans;
}
}
// Driver code
public static void Main(String[] args)
{
Console.Write(splitIntoPrimes("13499315")+ "\n");
Console.Write(splitIntoPrimes("43")+ "\n");
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript implementation of the above approach
// Function to check whether a string
// is a prime number or not
function checkPrime(number)
{
let num = String(number);
for (let i = 2; i * i <= num; i++)
if ((num % i) == 0)
return false;
return true;
}
// A recursive function to find the minimum
// number of segments the given string can
// be divided such that every segment is a prime
function splitIntoPrimes(number)
{
// If the number is null
if (number.length == 0)
return 0;
// checkPrime function is called to check if
// the number is a prime or not.
if (number.length <= 6 && checkPrime(number))
return 1;
else {
let numLen = number.length;
// A very large number denoting maximum
let ans = 1000000;
// Consider a minimum of 6 and length
// since the primes are less than 10 ^ 6
for (let i = 1; i <= 6 && i <= numLen; i++) {
if (checkPrime(number.substr(0, i))) {
// Recursively call the function
// to check for the remaining string
let val = splitIntoPrimes(number.substr(i));
if (val != -1) {
// Evaluating minimum splits
// into Primes for the suffix
ans = Math.min(ans, 1 + val);
}
}
}
// Checks if no combination found
if (ans == 1000000)
return -1;
return ans;
}
}
// Driver code
document.write(splitIntoPrimes("13499315") + "<br>");
document.write(splitIntoPrimes("43") + "<br>");
// This code is contributed by gfgking
</script>
Producción:
3 1
Complejidad del tiempo:
- La complejidad de tiempo para el enfoque anterior sería de O(N 5/2 ) donde N es la longitud de la string de entrada.
- La complejidad para encontrar recursivamente todas las combinaciones posibles es O(N 2 ) .
- Para cada combinación, para verificar si el número es un número primo o no, se usa un tiempo adicional O(N 0.5 ) .
- Esto hace que la complejidad del tiempo sea O(N 5/2 ) .
Enfoque de programación dinámica: se ve que el problema dado exhibe una propiedad de subproblema superpuesta. Por lo tanto, la programación dinámica se puede utilizar para resolver de manera eficiente esta pregunta.
Se define y utiliza una array splitDP[] donde splitDP[i] indica el número mínimo de divisiones requeridas en la string de prefijos de longitud ‘i’ para dividirla en la subdivisión principal.
La array splitDP[] se llena de la siguiente manera:
- Se usa un bucle for para iterar a través de todos los índices de la string dada.
- Para cada índice ‘i’ del bucle anterior, se itera otro bucle del 1 al 6 para comprobar si la substring del índice (i + j) forma un número primo o no.
- Si forma un número primo, entonces el valor en splitDP[] se actualiza como:
splitDP[i + j] = min(splitDP[i + j], 1 + splitDP[i]);
- Después de actualizar todos los valores de la array, el valor en el último índice es el número mínimo de divisiones para toda la string.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check whether a string
// is a prime number or not
bool checkPrime(string number)
{
int num = stoi(number);
for (int i = 2; i * i <= num; i++)
if ((num % i) == 0)
return false;
return true;
}
// A function to find the minimum
// number of segments the given string
// can be divided such that every
// segment is a prime
int splitIntoPrimes(string number)
{
int numLen = number.length();
// Declare a splitdp[] array
// and initialize to -1
int splitDP[numLen + 1];
memset(splitDP, -1, sizeof(splitDP));
// Build the DP table in
// a bottom-up manner
for (int i = 1; i <= numLen; i++) {
// Initially Check if the entire prefix is Prime
if (i <= 6 && checkPrime(number.substr(0, i)))
splitDP[i] = 1;
// If the Given Prefix can be split into Primes
// then for the remaining string from i to j
// Check if Prime. If yes calculate
// the minimum split till j
if (splitDP[i] != -1) {
for (int j = 1; j <= 6 && i + j <= numLen; j++) {
// To check if the substring from i to j
// is a prime number or not
if (checkPrime(number.substr(i, j))) {
// If it is a prime, then update the dp array
if (splitDP[i + j] == -1)
splitDP[i + j] = 1 + splitDP[i];
else
splitDP[i + j] = min(splitDP[i + j],
1 + splitDP[i]);
}
}
}
}
// Return the minimum number of splits
// for the entire string
return splitDP[numLen];
}
// Driver code
int main()
{
cout << splitIntoPrimes("13499315") << "\n";
cout << splitIntoPrimes("43") << "\n";
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
// Function to check whether a String
// is a prime number or not
static boolean checkPrime(String number)
{
if(number.length()==0)
return true;
int num = Integer.parseInt(number);
for (int i = 2; i * i <= num; i++)
if ((num % i) == 0)
return false;
return true;
}
// A function to find the minimum
// number of segments the given String
// can be divided such that every
// segment is a prime
static int splitIntoPrimes(String number)
{
int numLen = number.length();
// Declare a splitdp[] array
// and initialize to -1
int []splitDP = new int[numLen + 1];
Arrays.fill(splitDP, -1);
// Build the DP table in
// a bottom-up manner
for (int i = 1; i <= numLen; i++) {
// Initially Check if the entire prefix is Prime
if (i <= 6 && checkPrime(number.substring(0, i)))
splitDP[i] = 1;
// If the Given Prefix can be split into Primes
// then for the remaining String from i to j
// Check if Prime. If yes calculate
// the minimum split till j
if (splitDP[i] != -1) {
for (int j = 1; j <= 6 && i + j <= numLen; j++) {
// To check if the subString from i to j
// is a prime number or not
if (checkPrime(number.substring(i, i+j))) {
// If it is a prime, then update the dp array
if (splitDP[i + j] == -1)
splitDP[i + j] = 1 + splitDP[i];
else
splitDP[i + j] = Math.min(splitDP[i + j],
1 + splitDP[i]);
}
}
}
}
// Return the minimum number of splits
// for the entire String
return splitDP[numLen];
}
// Driver code
public static void main(String[] args)
{
System.out.print(splitIntoPrimes("13499315")+ "\n");
System.out.print(splitIntoPrimes("43")+ "\n");
}
}
// This code contributed by Princi Singh
Python3
# Python 3 implementation of the above approach
from math import sqrt
# Function to check whether a string
# is a prime number or not
def checkPrime(number):
if(len(number) == 0):
return True
num = int(number)
for i in range(2,int(sqrt(num)) + 1, 1):
if ((num % i) == 0):
return False
return True
# A function to find the minimum
# number of segments the given string
# can be divided such that every
# segment is a prime
def splitIntoPrimes(number):
numLen = len(number)
# Declare a splitdp[] array
# and initialize to -1
splitDP = [-1 for i in range(numLen + 1)]
# Build the DP table in
# a bottom-up manner
for i in range(1, numLen + 1, 1):
# Initially Check if the entire prefix is Prime
if (i <= 6 and checkPrime(number[0:i])):
splitDP[i] = 1
# If the Given Prefix can be split into Primes
# then for the remaining string from i to j
# Check if Prime. If yes calculate
# the minimum split till j
if (splitDP[i] != -1):
j = 1
while(j <= 6 and i + j <= numLen):
# To check if the substring from i to j
# is a prime number or not
if (checkPrime(number[i:i+j])):
# If it is a prime, then update the dp array
if (splitDP[i + j] == -1):
splitDP[i + j] = 1 + splitDP[i]
else:
splitDP[i + j] = min(splitDP[i + j], 1 + splitDP[i])
j += 1
# Return the minimum number of splits
# for the entire string
return splitDP[numLen]
# Driver code
if __name__ == '__main__':
print(splitIntoPrimes("13499315"))
print(splitIntoPrimes("43"))
# This code is contributed by Surendra_Gangwar
C#
// C# implementation of the above approach
using System;
class GFG{
// Function to check whether a String
// is a prime number or not
static bool checkPrime(String number)
{
if(number.Length==0)
return true;
int num = Int32.Parse(number);
for (int i = 2; i * i <= num; i++)
if ((num % i) == 0)
return false;
return true;
}
// A function to find the minimum
// number of segments the given String
// can be divided such that every
// segment is a prime
static int splitIntoPrimes(String number)
{
int numLen = number.Length;
// Declare a splitdp[] array
// and initialize to -1
int []splitDP = new int[numLen + 1];
for (int i = 0; i <= numLen; i++)
splitDP[i] = -1;
// Build the DP table in
// a bottom-up manner
for (int i = 1; i <= numLen; i++) {
// Initially Check if the entire prefix is Prime
if (i <= 6 && checkPrime(number.Substring(0, i)))
splitDP[i] = 1;
// If the Given Prefix can be split into Primes
// then for the remaining String from i to j
// Check if Prime. If yes calculate
// the minimum split till j
if (splitDP[i] != -1) {
for (int j = 1; j <= 6 && i + j <= numLen; j++) {
// To check if the subString from i to j
// is a prime number or not
if (checkPrime(number.Substring(i, j))) {
// If it is a prime, then update the dp array
if (splitDP[i + j] == -1)
splitDP[i + j] = 1 + splitDP[i];
else
splitDP[i + j] = Math.Min(splitDP[i + j],
1 + splitDP[i]);
}
}
}
}
// Return the minimum number of splits
// for the entire String
return splitDP[numLen];
}
// Driver code
public static void Main(String[] args)
{
Console.Write(splitIntoPrimes("13499315")+ "\n");
Console.Write(splitIntoPrimes("43")+ "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the above approach
// Function to check whether a String
// is a prime number or not
function checkPrime(number)
{
if (number.length == 0)
return true;
let num = parseInt(number);
for(let i = 2; i * i <= num; i++)
if ((num % i) == 0)
return false;
return true;
}
// A function to find the minimum
// number of segments the given String
// can be divided such that every
// segment is a prime
function splitIntoPrimes(number)
{
let numLen = number.length;
// Declare a splitdp[] array
// and initialize to -1
let splitDP = new Array(numLen + 1);
for(let i = 0; i < splitDP.length; i++)
{
splitDP[i] = -1;
}
// Build the DP table in
// a bottom-up manner
for(let i = 1; i <= numLen; i++)
{
// Initially Check if the entire prefix is Prime
if (i <= 6 && checkPrime(number.substring(0, i)))
splitDP[i] = 1;
// If the Given Prefix can be split into Primes
// then for the remaining String from i to j
// Check if Prime. If yes calculate
// the minimum split till j
if (splitDP[i] != -1)
{
for(let j = 1;
j <= 6 && i + j <= numLen;
j++)
{
// To check if the subString from i to j
// is a prime number or not
if (checkPrime(number.substring(i, i + j)))
{
// If it is a prime, then update the
// dp array
if (splitDP[i + j] == -1)
splitDP[i + j] = 1 + splitDP[i];
else
splitDP[i + j] = Math.min(
splitDP[i + j],
1 + splitDP[i]);
}
}
}
}
// Return the minimum number of splits
// for the entire String
return splitDP[numLen];
}
// Driver code
document.write(splitIntoPrimes("13499315") + "<br>");
document.write(splitIntoPrimes("43") + "<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3 1
Complejidad del tiempo:
- La complejidad temporal del enfoque anterior es O(N 3/2 ) donde N es la longitud de la string de entrada.
- El tiempo para iterar a través de todos los índices es O(N) .
- Dado que el bucle for interno se ejecuta un número constante de veces para cada índice, su tiempo de ejecución puede considerarse constante.
- Para cada índice, el tiempo necesario para verificar si el número es primo o no es de O(N 0.5 ) .
- Por lo tanto, la complejidad temporal total es O(N 3/2 ) .
Enfoque de programación dinámica optimizado: el enfoque anterior se puede optimizar aún más mediante el uso del concepto Tamiz de Eratóstenes para precalcular y almacenar si un número es primo o no y reducir la complejidad del tiempo para verificar un número en cada iteración.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to precompute all the primes
// upto 1000000 and store it in a set
// using Sieve of Eratosthenes
void getPrimesFromSeive(set<string>& primes)
{
bool prime[1000001];
memset(prime, true, sizeof(prime));
prime[0] = prime[1] = false;
for (int i = 2; i * i <= 1000000; i++) {
if (prime[i] == true) {
for (int j = i * i; j <= 1000000; j += i)
prime[j] = false;
}
}
// Here to_string() is used
// for converting int to string
for (int i = 2; i <= 1000000; i++) {
if (prime[i] == true)
primes.insert(to_string(i));
}
}
// A function to find the minimum
// number of segments the given string
// can be divided such that every
// segment is a prime
int splitIntoPrimes(string number)
{
int numLen = number.length();
// Declare a splitdp[] array
// and initialize to -1
int splitDP[numLen + 1];
memset(splitDP, -1, sizeof(splitDP));
// Call sieve function to store primes in
// primes array
set<string> primes;
getPrimesFromSeive(primes);
// Build the DP table in a bottom-up manner
for (int i = 1; i <= numLen; i++) {
// If the prefix is prime then the prefix
// will be found in the prime set
if (i <= 6 && (primes.find(number.substr(0, i))
!= primes.end()))
splitDP[i] = 1;
// If the Given Prefix can be split into Primes
// then for the remaining string from i to j
// Check if Prime. If yes calculate
// the minimum split till j
if (splitDP[i] != -1) {
for (int j = 1; j <= 6 && i + j <= numLen; j++) {
// To check if the substring from i to j
// is a prime number or not
if (primes.find(number.substr(i, j))
!= primes.end()) {
// If it is a prime, then update the dp array
if (splitDP[i + j] == -1)
splitDP[i + j] = 1 + splitDP[i];
else
splitDP[i + j] = min(splitDP[i + j],
1 + splitDP[i]);
}
}
}
}
// Return the minimum number of splits
// for the entire string
return splitDP[numLen];
}
int main()
{
cout << splitIntoPrimes("13499315") << "\n";
cout << splitIntoPrimes("43") << "\n";
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
// Function to precompute all the primes
// upto 1000000 and store it in a set
// using Sieve of Eratosthenes
static void getPrimesFromSeive(HashSet<String> primes)
{
boolean []prime = new boolean[1000001];
Arrays.fill(prime, true);
prime[0] = prime[1] = false;
for (int i = 2; i * i <= 1000000; i++) {
if (prime[i] == true) {
for (int j = i * i; j <= 1000000; j += i)
prime[j] = false;
}
}
// Here to_String() is used
// for converting int to String
for (int i = 2; i <= 1000000; i++) {
if (prime[i] == true)
primes.add(String.valueOf(i));
}
}
// A function to find the minimum
// number of segments the given String
// can be divided such that every
// segment is a prime
static int splitIntoPrimes(String number)
{
int numLen = number.length();
// Declare a splitdp[] array
// and initialize to -1
int []splitDP = new int[numLen + 1];
Arrays.fill(splitDP, -1);
// Call sieve function to store primes in
// primes array
HashSet<String> primes = new HashSet<String>();
getPrimesFromSeive(primes);
// Build the DP table in a bottom-up manner
for (int i = 1; i <= numLen; i++) {
// If the prefix is prime then the prefix
// will be found in the prime set
if (i <= 6 && (primes.contains(number.substring(0, i))))
splitDP[i] = 1;
// If the Given Prefix can be split into Primes
// then for the remaining String from i to j
// Check if Prime. If yes calculate
// the minimum split till j
if (splitDP[i] != -1) {
for (int j = 1; j <= 6 && i + j <= numLen; j++) {
// To check if the subString from i to j
// is a prime number or not
if (primes.contains(number.substring(i, i+j))) {
// If it is a prime, then update the dp array
if (splitDP[i + j] == -1)
splitDP[i + j] = 1 + splitDP[i];
else
splitDP[i + j] = Math.min(splitDP[i + j],
1 + splitDP[i]);
}
}
}
}
// Return the minimum number of splits
// for the entire String
return splitDP[numLen];
}
public static void main(String[] args)
{
System.out.print(splitIntoPrimes("13499315")+ "\n");
System.out.print(splitIntoPrimes("43")+ "\n");
}
}
// This code contributed by Princi Singh
Python3
# Python3 implementation of the above approach
# Function to precompute all the primes
# upto 1000000 and store it in a set
# using Sieve of Eratosthenes
def getPrimesFromSeive(primes):
prime = [True] * (1000001)
prime[0], prime[1] = False, False
i = 2
while (i * i <= 1000000):
if (prime[i] == True):
for j in range(i * i, 1000001, i):
prime[j] = False
i += 1
# Here str() is used for
# converting int to string
for i in range(2, 1000001):
if (prime[i] == True):
primes.append(str(i))
# A function to find the minimum
# number of segments the given string
# can be divided such that every
# segment is a prime
def splitIntoPrimes(number):
numLen = len(number)
# Declare a splitdp[] array
# and initialize to -1
splitDP = [-1] * (numLen + 1)
# Call sieve function to store
# primes in primes array
primes = []
getPrimesFromSeive(primes)
# Build the DP table in a bottom-up manner
for i in range(1, numLen + 1):
# If the prefix is prime then the prefix
# will be found in the prime set
if (i <= 6 and (number[0 : i] in primes)):
splitDP[i] = 1
# If the Given Prefix can be split into Primes
# then for the remaining string from i to j
# Check if Prime. If yes calculate
# the minimum split till j
if (splitDP[i] != -1):
j = 1
while (j <= 6 and (i + j <= numLen)):
# To check if the substring from i to j
# is a prime number or not
if (number[i : i + j] in primes):
# If it is a prime, then
# update the dp array
if (splitDP[i + j] == -1):
splitDP[i + j] = 1 + splitDP[i]
else:
splitDP[i + j] = min(splitDP[i + j],
1 + splitDP[i])
j += 1
# Return the minimum number of
# splits for the entire string
return splitDP[numLen]
# Driver code
print(splitIntoPrimes("13499315"))
print(splitIntoPrimes("43"))
# This code is contributed by chitranayal
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to precompute all the primes
// upto 1000000 and store it in a set
// using Sieve of Eratosthenes
static void getPrimesFromSeive(HashSet<String> primes)
{
bool []prime = new bool[1000001];
for(int i = 0; i < 1000001; i++)
prime[i] = true;
prime[0] = prime[1] = false;
for(int i = 2; i * i <= 1000000; i++)
{
if (prime[i] == true)
{
for(int j = i * i; j <= 1000000; j += i)
prime[j] = false;
}
}
// Converting int to String
for(int i = 2; i <= 1000000; i++)
{
if (prime[i] == true)
primes.Add(String.Join("", i));
}
}
// A function to find the minimum
// number of segments the given String
// can be divided such that every
// segment is a prime
static int splitIntoPrimes(String number)
{
int numLen = number.Length;
// Declare a splitdp[] array
// and initialize to -1
int []splitDP = new int[numLen + 1];
for(int i = 0; i < numLen + 1; i++)
splitDP[i] = -1;
// Call sieve function to store primes
// in primes array
HashSet<String> primes = new HashSet<String>();
getPrimesFromSeive(primes);
// Build the DP table in a bottom-up manner
for(int i = 1; i <= numLen; i++)
{
// If the prefix is prime then the prefix
// will be found in the prime set
if (i <= 6 && (primes.Contains
(number.Substring(0, i))))
splitDP[i] = 1;
// If the given prefix can be split into
// primes, then for the remaining String
// from i to j check if prime. If yes
// calculate the minimum split till j
if (splitDP[i] != -1)
{
for(int j = 1; j <= 6 && i + j <= numLen; j++)
{
// To check if the subString from
// i to j is a prime number or not
if (primes.Contains(number.Substring(i, j)))
{
// If it is a prime, then update
// the dp array
if (splitDP[i + j] == -1)
splitDP[i + j] = 1 + splitDP[i];
else
splitDP[i + j] = Math.Min(splitDP[i + j],
1 + splitDP[i]);
}
}
}
}
// Return the minimum number of
// splits for the entire String
return splitDP[numLen];
}
public static void Main(String[] args)
{
Console.Write(splitIntoPrimes("13499315") + "\n");
Console.Write(splitIntoPrimes("43") + "\n");
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript implementation of the above approach
// Function to precompute all the primes
// upto 1000000 and store it in a set
// using Sieve of Eratosthenes
function getPrimesFromSeive(primes)
{
let prime = new Array(1000001);
for(let i=0;i<prime.length;i++)
{
prime[i]=true;
}
prime[0] = prime[1] = false;
for (let i = 2; i * i <= 1000000; i++) {
if (prime[i] == true) {
for (let j = i * i; j <= 1000000; j += i)
prime[j] = false;
}
}
// Here to_String() is used
// for converting int to String
for (let i = 2; i <= 1000000; i++) {
if (prime[i] == true)
primes.add((i).toString());
}
}
// A function to find the minimum
// number of segments the given String
// can be divided such that every
// segment is a prime
function splitIntoPrimes(number)
{
let numLen = number.length;
// Declare a splitdp[] array
// and initialize to -1
let splitDP = new Array(numLen + 1);
for(let i=0;i<splitDP.length;i++)
{
splitDP[i]=-1;
}
// Call sieve function to store primes in
// primes array
let primes = new Set();
getPrimesFromSeive(primes);
// Build the DP table in a bottom-up manner
for (let i = 1; i <= numLen; i++) {
// If the prefix is prime then the prefix
// will be found in the prime set
if (i <= 6 && (primes.has(number.substring(0, i))))
splitDP[i] = 1;
// If the Given Prefix can be split into Primes
// then for the remaining String from i to j
// Check if Prime. If yes calculate
// the minimum split till j
if (splitDP[i] != -1) {
for (let j = 1; j <= 6 && i + j <= numLen; j++) {
// To check if the subString from i to j
// is a prime number or not
if (primes.has(number.substring(i, i+j))) {
// If it is a prime, then update the dp array
if (splitDP[i + j] == -1)
splitDP[i + j] = 1 + splitDP[i];
else
splitDP[i + j] = Math.min(splitDP[i + j],
1 + splitDP[i]);
}
}
}
}
// Return the minimum number of splits
// for the entire String
return splitDP[numLen];
}
document.write(splitIntoPrimes("13499315")+ "<br>");
document.write(splitIntoPrimes("43")+ "<br>");
// This code is contributed by rag2127
</script>
Producción:
3 1
Complejidad del tiempo:
- Este es el método más eficiente ya que se ejecuta en una complejidad de tiempo O(N) donde N es la longitud de la string de entrada.
- Dado que la criba de Eratóstenes tiene un tiempo de ejecución de O(N*log(log(N))) y la lista de primos hasta 10 6 , se puede calcular la complejidad del precálculo. Sin embargo, dado que esto se realiza solo una vez para cualquier número de strings, no se cuenta al calcular la complejidad del tiempo.