Cuente números del rango cuyos factores primos son solo 2 y 3 usando Arrays | conjunto 2

Dados dos enteros positivos L y R , la tarea es contar los elementos del rango [L, R] cuyos factores primos son solo 2 y 3 .
Ejemplos: 
 

Entrada: L = 1, R = 10 
Salida: 6 
Explicación: 
2 = 2 
3 = 3 
4 = 2 * 2 
6 = 2 * 3 
8 = 2 * 2 * 2 
9 = 3 * 3
Entrada: L = 100, R = 200 
Salida: 5 
 

Para un enfoque más simple, consulte Contar números del rango cuyos factores primos son solo 2 y 3 .
Enfoque: 
Para resolver el problema de manera optimizada, siga los pasos que se detallan a continuación: 
 

• Almacene todas las potencias de 2 que sean menores o iguales que R en una array power2[ ] .
• Del mismo modo, almacene todas las potencias de 3 que sean menores o iguales que R en otra array power3[] .
• Inicialice la tercera array power23[] y almacene el producto por pares de cada elemento de power2[] con cada elemento de power3[] que sea menor o igual que R .
• Ahora, para cualquier rango [L, R] , simplemente iteramos sobre el arreglo power23[] y contamos los números en el rango [L, R] .

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

// C++ program to count the elements
// in the range [L, R] whose prime
// factors are only 2 and 3.
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function which will calculate the
// elements in the given range
void calc_ans(ll l, ll r)
{
 
    vector<ll> power2, power3;
 
    // Store the current power of 2
    ll mul2 = 1;
    while (mul2 <= r) {
        power2.push_back(mul2);
        mul2 *= 2;
    }
 
    // Store the current power of 3
    ll mul3 = 1;
    while (mul3 <= r) {
        power3.push_back(mul3);
        mul3 *= 3;
    }
 
    // power23[] will store pairwise product of
    // elements of power2 and power3 that are <=r
    vector<ll> power23;
 
    for (int x = 0; x < power2.size(); x++) {
        for (int y = 0; y < power3.size(); y++) {
 
            ll mul = power2[x] * power3[y];
            if (mul == 1)
                continue;
 
            // Insert in power23][]
            // only if mul<=r
            if (mul <= r)
                power23.push_back(mul);
        }
    }
 
    // Store the required answer
    ll ans = 0;
    for (ll x : power23) {
        if (x >= l && x <= r)
            ans++;
    }
 
    // Print the result
    cout << ans << endl;
}
 
// Driver code
int main()
{
 
    ll l = 1, r = 10;
 
    calc_ans(l, r);
 
    return 0;
}

// Java program to count the elements
// in the range [L, R] whose prime
// factors are only 2 and 3.
import java.util.*;
class GFG{
 
// Function which will calculate the
// elements in the given range
static void calc_ans(int l, int r)
{
 
    Vector<Integer> power2 = new Vector<Integer>(),
                    power3 = new Vector<Integer>();
 
    // Store the current power of 2
    int mul2 = 1;
    while (mul2 <= r)
    {
        power2.add(mul2);
        mul2 *= 2;
    }
 
    // Store the current power of 3
    int mul3 = 1;
    while (mul3 <= r)
    {
        power3.add(mul3);
        mul3 *= 3;
    }
 
    // power23[] will store pairwise product of
    // elements of power2 and power3 that are <=r
    Vector<Integer> power23 = new Vector<Integer>();
 
    for (int x = 0; x < power2.size(); x++)
    {
        for (int y = 0; y < power3.size(); y++)
        {
            int mul = power2.get(x) *
                      power3.get(y);
            if (mul == 1)
                continue;
 
            // Insert in power23][]
            // only if mul<=r
            if (mul <= r)
                power23.add(mul);
        }
    }
 
    // Store the required answer
    int ans = 0;
    for (int x : power23)
    {
        if (x >= l && x <= r)
            ans++;
    }
 
    // Print the result
    System.out.print(ans + "\n");
}
 
// Driver code
public static void main(String[] args)
{
    int l = 1, r = 10;
 
    calc_ans(l, r);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to count the elements
# in the range [L, R] whose prime
# factors are only 2 and 3.
 
# Function which will calculate the
# elements in the given range
def calc_ans(l, r):
 
    power2 = []; power3 = [];
 
    # Store the current power of 2
    mul2 = 1;
    while (mul2 <= r):
        power2.append(mul2);
        mul2 *= 2;
 
    # Store the current power of 3
    mul3 = 1;
    while (mul3 <= r):
        power3.append(mul3);
        mul3 *= 3;
 
    # power23[] will store pairwise
    # product of elements of power2
    # and power3 that are <=r
    power23 = [];
 
    for x in range(len(power2)):
        for y in range(len(power3)):
 
            mul = power2[x] * power3[y];
            if (mul == 1):
                continue;
 
            # Insert in power23][]
            # only if mul<=r
            if (mul <= r):
                power23.append(mul);
 
    # Store the required answer
    ans = 0;
    for x in power23:
        if (x >= l and x <= r):
            ans += 1;
 
    # Print the result
    print(ans);
 
# Driver code
if __name__ == "__main__":
 
    l = 1; r = 10;
     
    calc_ans(l, r);
 
# This code is contributed by AnkitRai01

// C# program to count the elements
// in the range [L, R] whose prime
// factors are only 2 and 3.
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function which will calculate the
// elements in the given range
static void calc_ans(int l, int r)
{
 
    List<int> power2 = new List<int>(),
              power3 = new List<int>();
 
    // Store the current power of 2
    int mul2 = 1;
    while (mul2 <= r)
    {
        power2.Add(mul2);
        mul2 *= 2;
    }
 
    // Store the current power of 3
    int mul3 = 1;
    while (mul3 <= r)
    {
        power3.Add(mul3);
        mul3 *= 3;
    }
 
    // power23[] will store pairwise product of
    // elements of power2 and power3 that are <=r
    List<int> power23 = new List<int>();
 
    for (int x = 0; x < power2.Count; x++)
    {
        for (int y = 0; y < power3.Count; y++)
        {
            int mul = power2[x] *
                      power3[y];
            if (mul == 1)
                continue;
 
            // Insert in power23,]
            // only if mul<=r
            if (mul <= r)
                power23.Add(mul);
        }
    }
 
    // Store the required answer
    int ans = 0;
    foreach (int x in power23)
    {
        if (x >= l && x <= r)
            ans++;
    }
 
    // Print the result
    Console.Write(ans + "\n");
}
 
// Driver code
public static void Main(String[] args)
{
    int l = 1, r = 10;
 
    calc_ans(l, r);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to count the elements
// in the range [L, R] whose prime
// factors are only 2 and 3.
 
// Function which will calculate the
// elements in the given range
function calc_ans(l, r)
{
 
    var power2 = [], power3 = [];
 
    // Store the current power of 2
    var mul2 = 1;
    while (mul2 <= r) {
        power2.push(mul2);
        mul2 *= 2;
    }
 
    // Store the current power of 3
    var mul3 = 1;
    while (mul3 <= r) {
        power3.push(mul3);
        mul3 *= 3;
    }
 
    // power23[] will store pairwise product of
    // elements of power2 and power3 that are <=r
    var power23 = [];
 
    for (var x = 0; x < power2.length; x++) {
        for (var y = 0; y < power3.length; y++) {
 
            var mul = power2[x] * power3[y];
            if (mul == 1)
                continue;
 
            // Insert in power23][]
            // only if mul<=r
            if (mul <= r)
                power23.push(mul);
        }
    }
 
    // Store the required answer
    var ans = 0;
    power23.forEach(x => {
         
        if (x >= l && x <= r)
            ans++;
    });
 
    // Print the result
    document.write( ans );
}
 
// Driver code
var l = 1, r = 10;
calc_ans(l, r);
 
 
</script>

6

Complejidad de tiempo: O (log ₂ (R) * log ₃ (R)), ya que estamos atravesando bucles anidados donde incrementamos en múltiplos de 2 y 3.

Espacio auxiliar: O(log2(R) * log3(R)), ya que estamos usando espacio extra.
Nota: El enfoque se puede optimizar aún más. Después de almacenar potencias de 2 y 3, la respuesta se puede calcular utilizando dos punteros en lugar de generar todos los números.