Dados dos números enteros N y M , la tarea es realizar las siguientes operaciones:
- Para cada valor en el rango [N, M] , calcule la suma de sus factores primos seguida de la suma de los factores primos de esa suma y así sucesivamente.
- Genere la secuencia anterior para cada elemento de la array y calcule la longitud de la secuencia
Ilustración
N = 8
Factores primos = {2, 2, 2}. Suma = 2 + 2 + 2 = 6.
Factores primos de 6 = {2, 3}. Suma = 2 + 3 = 5.
Ahora 5 no se puede reducir más.
Por lo tanto, la secuencia es {8, 6, 5} . La longitud de la secuencia es 3 .
- Encuentre la longitud máxima de dicha subsecuencia generada.
Ejemplos:
Entrada: N = 5, M = 10
Salida: 3
Explicación:
Para N = 5, la secuencia es {5}, por lo que la longitud es 1
Para N = 6, la secuencia es {6, 5}, por lo que la longitud es 2
Para N = 7, la secuencia es {7}, por lo que la longitud es 1
Para N = 8, la secuencia es {8, 6, 5}, por lo que la longitud es 3
Para N = 9, la secuencia es {9, 6, 5}, entonces la longitud es 3
Para N = 10, la secuencia es {10, 7}, entonces la longitud es 2
Por lo tanto, la longitud máxima de la secuencia en este rango es 3.Entrada: N = 2, M = 14
Salida: 4
Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar sobre el rango [N, M] , y para cada número entero, encontrar sus factores primos y sumarlos y repetir esto para la suma obtenida recursivamente hasta una suma que en sí misma es se obtiene un primo.
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . Siga los pasos a continuación para resolver el problema:
- Calcule previamente los números primos utilizando el método de la criba de Eratóstenes .
- Calcule previamente los factores primos más pequeños de cada número entero para encontrar los factores primos, usando Factorización prima usando Sieve .
- Ahora, para cada número entero en el rango [N, M] , calcule la suma de los factores primos y repita recursivamente para la suma obtenida. Almacene la longitud de la secuencia en la array dp[] , para evitar volver a calcular. Si la suma obtenida es un número primo, almacene el cálculo adicional.
- Actualice la longitud máxima obtenida y repita el paso anterior para cada número en el rango [N, M] , excepto 4 , que conduce a un bucle infinito .
- Imprime la longitud máxima obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Smallest prime factor array
int spf[100005];
// Stores if a number is prime or not
bool prime[100005];
int dp[100005];
// Function to compute all primes
// using Sieve of Eratosthenes
void sieve()
{
prime[0] = prime[1] = false;
for (int i = 2; i < 100005; i++)
prime[i] = true;
for (int i = 2; i * i < 100005; i++) {
if (prime[i]) {
for (int j = i * i; j < 100005; j += i) {
prime[j] = false;
}
}
}
}
// Function for finding smallest
// prime factors for every integer
void smallestPrimeFactors()
{
for (int i = 0; i < 100005; i++)
spf[i] = -1;
for (int i = 2; i * i < 100005; i++) {
for (int j = i; j < 100005; j += i) {
if (spf[j] == -1) {
spf[j] = i;
}
}
}
}
// Function to find the sum of
// prime factors of number
int sumOfPrimeFactors(int n)
{
int ans = 0;
while (n > 1) {
// Add smallest prime
// factor to the sum
ans += spf[n];
// Reduce N
n /= spf[n];
}
// Return the answer
return ans;
}
// Function to return the length of
// sequence of for the given number
int findLength(int n)
{
// If the number is prime
if (prime[n]) {
return 1;
}
// If a previously computed
// subproblem occurred
if (dp[n]) {
return dp[n];
}
// Calculate the sum of
// prime factors
int sum = sumOfPrimeFactors(n);
return dp[n] = 1 + findLength(sum);
}
// Function to return the maximum length
// of sequence for the given range
int maxLength(int n, int m)
{
// Pre-calculate primes
sieve();
// Precalculate smallest
// prime factors
smallestPrimeFactors();
int ans = INT_MIN;
// Iterate over the range
for (int i = n; i <= m; i++) {
if (i == 4) {
continue;
}
// Update maximum length
ans = max(ans, findLength(i));
}
return ans;
}
// Driver Code
int main()
{
int n = 2, m = 14;
cout << maxLength(n, m);
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Smallest prime factor array
static int spf[] = new int[100005];
// Stores if a number is prime or not
static boolean prime[] = new boolean[100005];
static int dp[] = new int[100005];
// Function to compute all primes
// using Sieve of Eratosthenes
static void sieve()
{
prime[0] = prime[1] = false;
for (int i = 2; i < 100005; i++)
prime[i] = true;
for (int i = 2; i * i < 100005; i++)
{
if (prime[i])
{
for (int j = i * i; j < 100005; j += i)
{
prime[j] = false;
}
}
}
}
// Function for finding smallest
// prime factors for every integer
static void smallestPrimeFactors()
{
for (int i = 0; i < 100005; i++)
spf[i] = -1;
for (int i = 2; i * i < 100005; i++)
{
for (int j = i; j < 100005; j += i)
{
if (spf[j] == -1)
{
spf[j] = i;
}
}
}
}
// Function to find the sum of
// prime factors of number
static int sumOfPrimeFactors(int n)
{
int ans = 0;
while (n > 1)
{
// Add smallest prime
// factor to the sum
ans += spf[n];
// Reduce N
n /= spf[n];
}
// Return the answer
return ans;
}
// Function to return the length of
// sequence of for the given number
static int findLength(int n)
{
// If the number is prime
if (prime[n])
{
return 1;
}
// If a previously computed
// subproblem occurred
if (dp[n] != 0)
{
return dp[n];
}
// Calculate the sum of
// prime factors
int sum = sumOfPrimeFactors(n);
return dp[n] = 1 + findLength(sum);
}
// Function to return the maximum length
// of sequence for the given range
static int maxLength(int n, int m)
{
// Pre-calculate primes
sieve();
// Precalculate smallest
// prime factors
smallestPrimeFactors();
int ans = Integer.MIN_VALUE;
// Iterate over the range
for (int i = n; i <= m; i++)
{
if (i == 4)
{
continue;
}
// Update maximum length
ans = Math.max(ans, findLength(i));
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int n = 2, m = 14;
System.out.print(maxLength(n, m));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to implement # the above approach import sys # Smallest prime factor array spf = [0] * 100005 # Stores if a number is prime or not prime = [False] * 100005 dp = [0] * 100005 # Function to compute all primes # using Sieve of Eratosthenes def sieve(): for i in range(2, 100005): prime[i] = True i = 2 while i * i < 100005: if(prime[i]): for j in range(i * i, 100005, i): prime[j] = False i += 1 # Function for finding smallest # prime factors for every integer def smallestPrimeFactors(): for i in range(10005): spf[i] = -1 i = 2 while i * i < 100005: for j in range(i, 100005, i): if(spf[j] == -1): spf[j] = i i += 1 # Function to find the sum of # prime factors of number def sumOfPrimeFactors(n): ans = 0 while(n > 1): # Add smallest prime # factor to the sum ans += spf[n] # Reduce N n //= spf[n] # Return the answer return ans # Function to return the length of # sequence of for the given number def findLength(n): # If the number is prime if(prime[n]): return 1 # If a previously computed # subproblem occurred if(dp[n]): return dp[n] # Calculate the sum of # prime factors sum = sumOfPrimeFactors(n) dp[n] = 1 + findLength(sum) return dp[n] # Function to return the maximum length # of sequence for the given range def maxLength(n, m): # Pre-calculate primes sieve() # Precalculate smallest # prime factors smallestPrimeFactors() ans = -sys.maxsize - 1 # Iterate over the range for i in range(n, m + 1): if(i == 4): continue # Update maximum length ans = max(ans, findLength(i)) return ans # Driver Code n = 2 m = 14 # Function call print(maxLength(n, m)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Smallest prime factor array
static int []spf = new int[100005];
// Stores if a number is prime or not
static bool []prime = new bool[100005];
static int []dp = new int[100005];
// Function to compute all primes
// using Sieve of Eratosthenes
static void sieve()
{
prime[0] = prime[1] = false;
for(int i = 2; i < 100005; i++)
prime[i] = true;
for(int i = 2; i * i < 100005; i++)
{
if (prime[i])
{
for(int j = i * i; j < 100005; j += i)
{
prime[j] = false;
}
}
}
}
// Function for finding smallest
// prime factors for every integer
static void smallestPrimeFactors()
{
for(int i = 0; i < 100005; i++)
spf[i] = -1;
for(int i = 2; i * i < 100005; i++)
{
for(int j = i; j < 100005; j += i)
{
if (spf[j] == -1)
{
spf[j] = i;
}
}
}
}
// Function to find the sum of
// prime factors of number
static int sumOfPrimeFactors(int n)
{
int ans = 0;
while (n > 1)
{
// Add smallest prime
// factor to the sum
ans += spf[n];
// Reduce N
n /= spf[n];
}
// Return the answer
return ans;
}
// Function to return the length of
// sequence of for the given number
static int findLength(int n)
{
// If the number is prime
if (prime[n])
{
return 1;
}
// If a previously computed
// subproblem occurred
if (dp[n] != 0)
{
return dp[n];
}
// Calculate the sum of
// prime factors
int sum = sumOfPrimeFactors(n);
return dp[n] = 1 + findLength(sum);
}
// Function to return the maximum length
// of sequence for the given range
static int maxLength(int n, int m)
{
// Pre-calculate primes
sieve();
// Precalculate smallest
// prime factors
smallestPrimeFactors();
int ans = int.MinValue;
// Iterate over the range
for(int i = n; i <= m; i++)
{
if (i == 4)
{
continue;
}
// Update maximum length
ans = Math.Max(ans, findLength(i));
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int n = 2, m = 14;
Console.Write(maxLength(n, m));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Smallest prime factor array
let spf = Array.from({length: 100005}, (_, i) => 0);
// Stores if a number is prime or not
let prime = Array.from({length: 100005}, (_, i) => 0);
let dp = Array.from({length: 100005}, (_, i) => 0);
// Function to compute all primes
// using Sieve of Eratosthenes
function sieve()
{
prime[0] = prime[1] = false;
for (let i = 2; i < 100005; i++)
prime[i] = true;
for (let i = 2; i * i < 100005; i++)
{
if (prime[i])
{
for (let j = i * i; j < 100005; j += i)
{
prime[j] = false;
}
}
}
}
// Function for finding smallest
// prime factors for every integer
function smallestPrimeFactors()
{
for (let i = 0; i < 100005; i++)
spf[i] = -1;
for (let i = 2; i * i < 100005; i++)
{
for (let j = i; j < 100005; j += i)
{
if (spf[j] == -1)
{
spf[j] = i;
}
}
}
}
// Function to find the sum of
// prime factors of number
function sumOfPrimeFactors(n)
{
let ans = 0;
while (n > 1)
{
// Add smallest prime
// factor to the sum
ans += spf[n];
// Reduce N
n /= spf[n];
}
// Return the answer
return ans;
}
// Function to return the length of
// sequence of for the given number
function findLength(n)
{
// If the number is prime
if (prime[n])
{
return 1;
}
// If a previously computed
// subproblem occurred
if (dp[n] != 0)
{
return dp[n];
}
// Calculate the sum of
// prime factors
let sum = sumOfPrimeFactors(n);
return dp[n] = 1 + findLength(sum);
}
// Function to return the maximum length
// of sequence for the given range
function maxLength(n, m)
{
// Pre-calculate primes
sieve();
// Precalculate smallest
// prime factors
smallestPrimeFactors();
let ans = Number.MIN_VALUE;
// Iterate over the range
for (let i = n; i <= m; i++)
{
if (i == 4)
{
continue;
}
// Update maximum length
ans = Math.max(ans, findLength(i));
}
return ans;
}
// Driver Code
let n = 2, m = 14;
document.write(maxLength(n, m));
</script>
Producción:
4
Complejidad temporal: O((NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por VikasVishwakarma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA