Recuento de números en el rango [L, R] con solo 2 o 7 como factores primos

Dados dos números enteros L y R , la tarea es encontrar el conteo de números en el rango [L, R] que tienen solo 2 o 7 como sus factores primos .

Ejemplos:

Entrada: L = 0, R = 0
Salida: 0 
Explicación: 0 no es divisible por 2 o 7

Entrada: L = 0, R = 2
Salida: 1 
Explicación: Solo 2 es el número entre el rango que tiene 2 como factor, por lo tanto, la cuenta es 1.

Entrada: L = 1, R = 15
Salida: 5
Explicación: 2, 4, 7, 8 y 14 son los números que tienen factores como 2 o 7, por lo tanto, la cuenta es 5

Enfoque ingenuo: el enfoque simple es generar todos los factores primos de cada número en el rango [L, R] y verificar si los factores son solo 2 o 7.

Siga los pasos para resolver el problema:

• Poligonal de i = L a R :
  • Almacene todos los factores primos de i en un vector (digamos factores ).
  • Atraviese el vector para ver si hay factores distintos de 2 o 7 presentes o no.
  • Si i es divisible por solo 2 o 7 , entonces incremente el conteo de lo contrario.
• Devuelve par de especial y regular como respuesta final.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find regular or special numbers
pair<int,int> SpecialorRegular(int L, int R)
{
    int regular = 0, special = 0, temp, i, j;
    vector<int>factors;
     
    // Base cases
    if(L > R || L < 0|| R < 0)
    return {-1, -1};
    else if(R < 2)
    regular += R - L + 1;
    else regular += 2 - L;
    L = 2;
     
    for(i = L; i <= R; i++){
        temp = i;
        factors.clear();
         
        for(j = 2; j * j <= i; j++)
        {
            while(temp % j == 0){
            factors.push_back(j);
            temp /= j;
            }
        }
        if(temp > 1)
        factors.push_back(temp);
         
        for(j = 0; j < factors.size(); j++){
            if(factors[j] != 7
               && factors[j] != 2)
            break;
        }
         
        if(j == factors.size())
        special++;
        else regular++;
    }
     
    return {special, regular};
}
 
//Function to print
void print(int L, int R){
    pair<int, int>ans
        = SpecialorRegular(L, R);
    cout << ans.first;
}
 
//Driver code
int main()
{
    int L = 0;
    int R = 2;
     
    // Function Call
    print(L, R);
    return 0;
}

// Java program for above approach
import java.util.ArrayList;
 
class GFG {
 
  // Function to find regular or special numbers
  static int[] SpecialorRegular(int L, int R)
  {
    int regular = 0, special = 0, temp, i, j;
    ArrayList<Integer> factors
      = new ArrayList<Integer>();
 
    // Base cases
    if (L > R || L < 0 || R < 0) {
      int[] pair = { -1, -1 };
      return pair;
    }
    else if (R < 2)
      regular += R - L + 1;
    else
      regular += 2 - L;
    L = 2;
 
    for (i = L; i <= R; i++) {
      temp = i;
      factors.clear();
 
      for (j = 2; j * j <= i; j++) {
        while (temp % j == 0) {
          factors.add(j);
          temp /= j;
        }
      }
      if (temp > 1)
        factors.add(temp);
 
      for (j = 0; j < factors.size(); j++) {
        if ((factors.get(j) != 7)
            && (factors.get(j) != 2))
          break;
      }
 
      if (j == factors.size())
        special++;
      else
        regular++;
    }
 
    int[] pair = { special, regular };
    return pair;
  }
 
  // Function to print
  static void print(int L, int R)
  {
    int[] ans = SpecialorRegular(L, R);
    System.out.print(ans[0]);
  }
 
  // driver code
  public static void main(String[] args)
  {
    int L = 0;
    int R = 2;
 
    // Function Call
    print(L, R);
  }
}
 
// This code is contributed by phasing17

# Python3 code for the above approach
 
# Function to find regular or special numbers
def SpecialorRegular(L, R):
    regular, special = 0, 0
    factors = []
     
    # base cases
    if L > R or L < 0 or R < 0:
        return [-1, -1]
    elif R < 2:
        regular += R - L + 1
    else:
        regular += 2 - L
    L = 2
    for i in range(L, R + 1):
        temp = i
        factors = []
        for j in range(2, 1 + int(i ** 0.5)):
            while not temp % j:
                factors.append(j)
                temp //= j
        if temp > 1:
            factors.append(temp)
        j = 0
        while j < len(factors):
            if factors[j] != 7 and factors[j] != 2:
                break
            j += 1
        if j == len(factors):
            special += 1
        else:
            regular += 1
    return [special, regular]
   
# Function to print
def prints(L, R):
    ans = SpecialorRegular(L, R)
    print(ans[0])
 
# Driver code
L, R = 0, 2
 
# Function Call
prints(L, R)
 
# This code is contributed by phasing17

<script>
    // JavaScript code for the above approach
 
    // Function to find regular or special numbers
    const SpecialorRegular = (L, R) => {
        let regular = 0, special = 0, temp, i, j;
        let factors = [];
 
        // Base cases
        if (L > R || L < 0 || R < 0)
            return [-1, -1];
        else if (R < 2)
            regular += R - L + 1;
        else regular += 2 - L;
        L = 2;
 
        for (i = L; i <= R; i++) {
            temp = i;
            factors = [];
 
            for (j = 2; j * j <= i; j++) {
                while (temp % j == 0) {
                    factors.push(j);
                    temp = parseInt(temp / j);
                }
            }
            if (temp > 1)
                factors.push(temp);
 
            for (j = 0; j < factors.length; j++) {
                if (factors[j] != 7
                    && factors[j] != 2)
                    break;
            }
 
            if (j == factors.length)
                special++;
            else regular++;
        }
 
        return [special, regular];
    }
 
    // Function to print
    const print = (L, R) => {
        let ans = SpecialorRegular(L, R);
        document.write(ans[0]);
    }
 
    // Driver code
 
    let L = 0;
    let R = 2;
 
    // Function Call
    print(L, R);
 
// This code is contributed by rakeshsahni
 
</script>

1

Complejidad del tiempo:O((R – L) ^{(3 / 2)} )
Espacio Auxiliar:O(registro R)

Enfoque eficiente: el problema se puede resolver de manera más eficiente siguiendo la observación mencionada:

Observación:

Genere todos los números de la forma 2*k o 7*k o 2*7*k usando recursividad donde k también está en una de las tres formas anteriores.

Siga los pasos para resolver el problema:

• Inicialice un mapa desordenado como visitado para almacenar los números ya visitados y cuente como 0 para almacenar el recuento de dichos números.
• Prepare una función recursiva para generar los números como se muestra en la observación.
• Si un número generado (digamos temp ) es:
  • Dentro del rango [L, R] y aún no visitado, márquelo como visitado e incremente el conteo .
  • Excede R o ya está visitado regresa de esa recursión y prueba otras opciones.
• Devuelve el conteo como la respuesta final requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
int special = 0;
unordered_map<int, bool> visited;
 
// Function to find special numbers
void countSpecial(int L, int R, int temp)
{
 
    // Base cases
    if (L > R) {
        special = -1;
        return;
    }
    else if (L < 0 || R < 0) {
        special = -1;
        return;
    }
    else if (temp > R)
        return;
 
    if (L <= temp && temp <= R && temp != 1
        && !visited[temp]) {
        special++;
        visited[temp] = 1;
    }
 
    countSpecial(L, R, temp * 2);
    countSpecial(L, R, temp * 7);
}
 
// Print function
void print(int L, int R)
{
    countSpecial(L, R, 1);
    if (special == -1)
        cout << -1 << " " << -1;
    else
        cout << special;
}
 
// Driver code
int main()
{
    int L = 0;
    int R = 2;
 
    // Function call
    print(L, R);
    return 0;
}

// Java program for above approach
import java.io.*;
import java.util.*;
import java.util.ArrayList;
 
class GFG {
 
static int special = 0;
private static HashMap<Integer, Boolean> visited = new HashMap<>();
  
// Function to find special numbers
static void countSpecial(int L, int R, int temp)
{
  
    // Base cases
    if (L > R) {
        special = -1;
        return;
    }
    else if (L < 0 || R < 0) {
        special = -1;
        return;
    }
    else if (temp > R)
        return;
     
    if (L <= temp && temp <= R && temp != 1 && !visited.containsKey(temp)) {
        special++;
        visited.put(temp,true);
    }
  
    countSpecial(L, R, temp * 2);
    countSpecial(L, R, temp * 7);
}
// Function to print
static void print(int L, int R)
{
    countSpecial(L, R, 1);
    if (special == -1)
    System.out.print("-1 -1");
    else
         System.out.print(special);
}
 
// driver code
public static void main(String[] args)
{
    int L = 0;
    int R = 2;
 
    // Function Call
    print(L, R);
}
}
 
// This code is contributed by Pushpesh Raj

# Python code for the above approach
special = 0
visited = {}
 
# Function to find special numbers
def countSpecial(L, R, temp):
 
    global special, visited
 
    # Base cases
    if (L > R):
        special = -1
        return
 
    elif (L < 0 or R < 0):
        special = -1
        return
 
    elif (temp > R):
        return
 
    if (L <= temp and temp <= R and temp != 1 and temp not in visited):
        special += 1
        visited[temp] = 1
 
    countSpecial(L, R, temp * 2)
    countSpecial(L, R, temp * 7)
 
# Print function
def Print(L, R):
    countSpecial(L, R, 1)
    if (special == -1):
        print("-1" + " " + "-1")
    else:
        print(special)
 
# Driver code
L = 0
R = 2
 
# Function call
Print(L, R)
 
# This code is contributed by shinjanpatra

<script>
       // JavaScript code for the above approach
       let special = 0;
       let visited = new Map();
 
       // Function to find special numbers
       function countSpecial(L, R, temp) {
 
           // Base cases
           if (L > R) {
               special = -1;
               return;
           }
           else if (L < 0 || R < 0) {
               special = -1;
               return;
           }
           else if (temp > R)
               return;
 
           if (L <= temp && temp <= R && temp != 1
               && !visited.has(temp)) {
               special++;
               visited.set(temp,1);
           }
 
           countSpecial(L, R, temp * 2);
           countSpecial(L, R, temp * 7);
       }
 
       // Print function
       function print(L, R) {
           countSpecial(L, R, 1);
           if (special == -1)
               document.write("-1" + " " + "-1");
           else
               document.write(special);
       }
 
       // Driver code
       let L = 0;
       let R = 2;
 
       // Function call
       print(L, R);
 
   // This code is contributed by Potta Lokesh
   </script>

1

Tiempo Complejidad: O(R)
Espacio Auxiliar:O (R – L)