Contar números del rango cuyos factores primos son solo 2 y 3

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:
2 = 2 
3 = 3 
4 = 2 * 2 
6 = 2 * 3 
8 = 2 * 2 * 2 
9 = 3 * 3
Entrada: L = 100, R = 200 
Salida :
 

Enfoque: inicie un ciclo de L a R y para cada elemento num
 

  • Si bien num es divisible por 2 , divídalo por 2 .
  • Si bien num es divisible por 3 , divídalo por 3 .
  • Si num = 1 entonces incremente el conteo ya que num tiene solo 2 y 3 como sus factores primos.

Imprime el conteo al final.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program to count the numbers within a range
// whose prime factors are only 2 and 3
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number within a range
// whose prime factors are only 2 and 3
int findTwoThreePrime(int l, int r)
{
    // Start with 2 so that 1 doesn't get counted
    if (l == 1)
        l++;
 
    int count = 0;
 
    for (int i = l; i <= r; i++) {
        int num = i;
 
        // While num is divisible by 2, divide it by 2
        while (num % 2 == 0)
            num /= 2;
 
        // While num is divisible by 3, divide it by 3
        while (num % 3 == 0)
            num /= 3;
 
        // If num got reduced to 1 then it has
        // only 2 and 3 as prime factors
        if (num == 1)
            count++;
    }
 
    return count;
}
 
// Driver code
int main()
{
    int l = 1, r = 10;
    cout << findTwoThreePrime(l, r);
    return 0;
}

Java

//Java program to count the numbers within a range
// whose prime factors are only 2 and 3
 
import java.io.*;
 
class GFG {
     
// Function to count the number within a range
// whose prime factors are only 2 and 3
static int findTwoThreePrime(int l, int r)
{
    // Start with 2 so that 1 doesn't get counted
    if (l == 1)
        l++;
 
    int count = 0;
 
    for (int i = l; i <= r; i++) {
        int num = i;
 
        // While num is divisible by 2, divide it by 2
        while (num % 2 == 0)
            num /= 2;
 
        // While num is divisible by 3, divide it by 3
        while (num % 3 == 0)
            num /= 3;
 
        // If num got reduced to 1 then it has
        // only 2 and 3 as prime factors
        if (num == 1)
            count++;
    }
 
    return count;
}
 
// Driver code
    public static void main (String[] args) {
 
        int l = 1, r = 10;
        System.out.println (findTwoThreePrime(l, r));
    }
//This code is contributed by ajit   
}

Python3

# Python3 program to count the numbers
# within a range whose prime factors
# are only 2 and 3
 
# Function to count the number within
# a range whose prime factors are only
# 2 and 3
def findTwoThreePrime(l, r) :
 
    # Start with 2 so that 1
    # doesn't get counted
    if (l == 1) :
        l += 1
 
    count = 0
 
    for i in range(l, r + 1) :
        num = i
 
        # While num is divisible by 2,
        # divide it by 2
        while (num % 2 == 0) :
            num //= 2;
 
        # While num is divisible by 3,
        # divide it by 3
        while (num % 3 == 0) :
            num //= 3
 
        # If num got reduced to 1 then it has
        # only 2 and 3 as prime factors
        if (num == 1) :
            count += 1
 
    return count
 
# Driver code
if __name__ == "__main__" :
 
    l = 1
    r = 10
     
    print(findTwoThreePrime(l, r))
     
# This code is contributed by Ryuga

C#

// C# program to count the numbers
// within a range whose prime factors
// are only 2 and 3
using System;
 
class GFG
{
         
// Function to count the number
// within a range whose prime
// factors are only 2 and 3
static int findTwoThreePrime(int l, int r)
{
    // Start with 2 so that 1
    // doesn't get counted
    if (l == 1)
        l++;
 
    int count = 0;
 
    for (int i = l; i <= r; i++)
    {
        int num = i;
 
        // While num is divisible by 2,
        // divide it by 2
        while (num % 2 == 0)
            num /= 2;
 
        // While num is divisible by 3,
        // divide it by 3
        while (num % 3 == 0)
            num /= 3;
 
        // If num got reduced to 1 then it 
        // has only 2 and 3 as prime factors
        if (num == 1)
            count++;
    }
    return count;
}
 
// Driver code
static public void Main ()
{
    int l = 1, r = 10;
    Console.WriteLine(findTwoThreePrime(l, r));
}
}
 
// This code is contributed by akt_mit

PHP

<?php
// PHP program to count the numbers
// within a range whose prime factors
// are only 2 and 3
 
// Function to count the number
// within a range whose prime
// factors are only 2 and 3
function findTwoThreePrime($l, $r)
{
    // Start with 2 so that 1
    // doesn't get counted
    if ($l == 1)
        $l++;
 
    $count = 0;
 
    for ($i = $l; $i <= $r; $i++)
    {
        $num = $i;
 
        // While num is divisible by 2,
        // divide it by 2
        while ($num % 2 == 0)
            $num /= 2;
 
        // While num is divisible by 3,
        // divide it by 3
        while ($num % 3 == 0)
            $num /= 3;
 
        // If num got reduced to 1 then it has
        // only 2 and 3 as prime factors
        if ($num == 1)
            $count++;
    }
    return $count;
}
 
// Driver code
$l = 1;
$r = 10;
echo findTwoThreePrime($l, $r);
     
// This code is contributed by ajit
?>

Javascript

<script>
 
    // Javascript program to count the numbers
    // within a range whose prime factors
    // are only 2 and 3
     
    // Function to count the number
    // within a range whose prime
    // factors are only 2 and 3
    function findTwoThreePrime(l, r)
    {
        // Start with 2 so that 1
        // doesn't get counted
        if (l == 1)
            l++;
 
        let count = 0;
 
        for (let i = l; i <= r; i++)
        {
            let num = i;
 
            // While num is divisible by 2,
            // divide it by 2
            while (num % 2 == 0)
                num = parseInt(num / 2, 10);
 
            // While num is divisible by 3,
            // divide it by 3
            while (num % 3 == 0)
                num = parseInt(num / 3, 10);
 
            // If num got reduced to 1 then it 
            // has only 2 and 3 as prime factors
            if (num == 1)
                count++;
        }
        return count;
    }
     
    let l = 1, r = 10;
    document.write(findTwoThreePrime(l, r));
     
</script>

Complejidad de tiempo: O((rl)*log2(rl))

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.

Publicación traducida automáticamente

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