Encuentra múltiplos de 2 o 3 o 5 menores o iguales a N

Posted on by Rudeus Greyrat

Dado un número entero  N . La tarea es contar todos los números que son menores o iguales a N que son divisibles por cualquiera de 2, 3 o 5.
Nota : si un número menor que N es divisible por 2 o 3, o 3 o 5, o todos los de 2,3 y 5 entonces también debe contarse una sola vez.
Ejemplos : 
 

Input : N = 5
Output : 4

Input : N = 10
Output : 8

Enfoque simple: un enfoque simple es atravesar de 1 a N y contar múltiplos de 2, 3, 5 que son menos que iguales a N. Para hacer esto, itere hasta N y simplemente verifique si un número es divisible por 2 o 3 o 5. Si es divisible, incrementa el contador y después de llegar a N, imprime el resultado.
Complejidad temporal : O(N).
Enfoque eficiente: un enfoque eficiente es utilizar el concepto de teoría de conjuntos. Como tenemos que encontrar números que sean divisibles por 2 o 3 o 5.
 

Picture

\begin{document} \begin{itemize} \item Let $n(a) \colon $ count of numbers divisible by 2. \item Let $n(b) \colon $ count of numbers divisible by 3. \item Let $n(c) \colon $ count of numbers divisible by 5. \item $n(a \bigcap b) \colon $ count of numbers divisible by 2 and 3. \item $n(a \bigcap c) \colon $ count of numbers divisible by 2 and 5. \item $n(b \bigcap c) \colon $ count of numbers divisible by 3 and 5. \item $n(a \bigcap b \bigcap c) \colon $ count of numbers divisible by 2 and 3 and 5. \end{itemize} According to set theory, $n\left( a \bigcup b \bigcup c \right)=n(a)+n(b)+n(c)-n(a \bigcap b)-n(b \bigcap c)-n(a \bigcap c)+n(a \bigcap b \bigcap c)$ \end{document}
Now the task is to find n(a),n(b),n(c),n(a\bigcap b), n(b\bigcap c), n(a\bigcap c), and n(a\bigcap b\bigcap c). All these terms can be calculated using Bit masking. In this problem we have taken three numbers 2,3, and 5. So, the bit mask should be of 2^3 bits i.e 8 to generate all combination of 2,3, and 5.
Now according to the formula of set union, all terms containing odd numbers of (2,3,5) will add into the result and terms containing even number of (2,3,5) will get subtracted.
Below is the implementation of the above approach: 
 

C++

// CPP program to count number of multiples
// of 2 or 3 or 5 less than or equal to N
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to count number of multiples
// of 2 or 3 or 5 less than or equal to N
int countMultiples(int n)
{
    // As we have to check divisibility
    // by three numbers, So we can implement
    // bit masking
    int multiple[] = { 2, 3, 5 };
     
    int count = 0, mask = pow(2, 3);
     
    for (int i = 1; i < mask; i++) {
 
        // we check whether jth bit
        // is set or not, if jth bit
        // is set, simply multiply
        // to prod
        int prod = 1;
         
        for (int j = 0; j < 3; j++) {
 
            // check for set bit
            if (i & 1 << j)
                prod = prod * multiple[j];
        }
         
        // check multiple of product
        if (__builtin_popcount(i) % 2 == 1)
            count = count + n / prod;
        else
            count = count - n / prod;
    }
     
    return count;
}
 
// Driver code
int main()
{
    int n = 10;
     
    cout << countMultiples(n) << endl;
     
    return 0;
}

Java

// Java program to count number of multiples
// of 2 or 3 or 5 less than or equal to N
 
class GFG{
static int count_setbits(int N)
{
    int cnt=0;
    while(N>0)
    {
        cnt+=(N&1);
        N=N>>1;
    }
    return cnt;
}
 
// Function to count number of multiples
// of 2 or 3 or 5 less than or equal to N
static int countMultiples(int n)
{
    // As we have to check divisibility
    // by three numbers, So we can implement
    // bit masking
    int multiple[] = { 2, 3, 5 };
     
    int count = 0, mask = (int)Math.pow(2, 3);
     
    for (int i = 1; i < mask; i++) {
 
        // we check whether jth bit
        // is set or not, if jth bit
        // is set, simply multiply
        // to prod
        int prod = 1;
         
        for (int j = 0; j < 3; j++) {
 
            // check for set bit
            if ((i & 1 << j)>0)
                prod = prod * multiple[j];
        }
         
        // check multiple of product
        if (count_setbits(i) % 2 == 1)
            count = count + n / prod;
        else
            count = count - n / prod;
    }
     
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 10;
     
    System.out.println(countMultiples(n));
}
}
// this code is contributed by mits

Python 3

# Python3 program to count number of multiples
# of 2 or 3 or 5 less than or equal to N
 
 
# Function to count number of multiples
# of 2 or 3 or 5 less than or equal to N
def countMultiples( n):
 
    # As we have to check divisibility
    # by three numbers, So we can implement
    # bit masking
    multiple = [ 2, 3, 5 ]
     
    count = 0
    mask = int(pow(2, 3))
    for i in range(1,mask):
        # we check whether jth bit
        # is set or not, if jth bit
        # is set, simply multiply
        # to prod
        prod = 1
        for j in range(3):
 
            # check for set bit
            if (i & (1 << j)):
                prod = prod * multiple[j]
         
        # check multiple of product
        if (bin(i).count('1') % 2 == 1):
            count = count + n // prod
        else:
            count = count - n // prod
     
    return count
 
 
# Driver code
if __name__=='__main__':
    n = 10
    print(countMultiples(n))
     
# This code is contributed by ash264

C#

// C#  program to count number of multiples
// of 2 or 3 or 5 less than or equal to N
 
 
using System;
 
public class GFG{
    static int count_setbits(int N)
{
    int cnt=0;
    while(N>0)
    {
        cnt+=(N&1);
        N=N>>1;
    }
    return cnt;
}
 
// Function to count number of multiples
// of 2 or 3 or 5 less than or equal to N
static int countMultiples(int n)
{
    // As we have to check divisibility
    // by three numbers, So we can implement
    // bit masking
    int []multiple = { 2, 3, 5 };
     
    int count = 0, mask = (int)Math.Pow(2, 3);
     
    for (int i = 1; i < mask; i++) {
 
        // we check whether jth bit
        // is set or not, if jth bit
        // is set, simply multiply
        // to prod
        int prod = 1;
         
        for (int j = 0; j < 3; j++) {
 
            // check for set bit
            if ((i & 1 << j)>0)
                prod = prod * multiple[j];
        }
         
        // check multiple of product
        if (count_setbits(i) % 2 == 1)
            count = count + n / prod;
        else
            count = count - n / prod;
    }
     
    return count;
}
 
// Driver code
    static public void Main (){
         
    int n = 10;
     
    Console.WriteLine(countMultiples(n));
}
}
//This code is contributed by ajit.

PHP

<?php
// PHP program to count number
// of multiples of 2 or 3 or 5
// less than or equal to N
 
// Bit count function
function popcount($value)
{
    $count = 0;
    while($value)
    {
        $count += ($value & 1);
        $value = $value >> 1;
    }
 
    return $count;
}
 
// Function to count number of 
// multiples of 2 or 3 or 5 less
// than or equal to N
function countMultiples($n)
{
    // As we have to check divisibility
    // by three numbers, So we can
    // implement bit masking
    $multiple = array(2, 3, 5);
     
    $count = 0;
    $mask = pow(2, 3);
     
    for ($i = 1; $i < $mask; $i++)
    {
 
        // we check whether jth bit
        // is set or not, if jth bit
        // is set, simply multiply
        // to prod
        $prod = 1;
         
        for ($j = 0; $j < 3; $j++)
        {
 
            // check for set bit
            if ($i & 1 << $j)
                $prod = $prod * $multiple[$j];
        }
         
        // check multiple of product
        if (popcount($i) % 2 == 1)
            $count = $count + (int)($n / $prod);
             
        else
            $count = $count - (int)($n / $prod);
             
    }
     
    return $count;
}
 
// Driver code
$n = 10;
     
echo countMultiples($n);
     
// This code is contributed by ash264
?>

Javascript

<script>
 
// javascript program to count number of multiples
// of 2 or 3 or 5 less than or equal to N
function count_setbits(N)
{
    var cnt=0;
    while(N>0)
    {
        cnt+=(N&1);
        N=N>>1;
    }
    return cnt;
}
 
// Function to count number of multiples
// of 2 or 3 or 5 less than or equal to N
function countMultiples(n)
{
    // As we have to check divisibility
    // by three numbers, So we can implement
    // bit masking
    var multiple = [ 2, 3, 5 ];
     
    var count = 0, mask = parseInt(Math.pow(2, 3));
     
    for (i = 1; i < mask; i++) {
 
        // we check whether jth bit
        // is set or not, if jth bit
        // is set, simply multiply
        // to prod
        var prod = 1;
         
        for (j = 0; j < 3; j++) {
 
            // check for set bit
            if ((i & 1 << j)>0)
                prod = prod * multiple[j];
        }
         
        // check multiple of product
        if (count_setbits(i) % 2 == 1)
            count = count + parseInt(n / prod);
        else
            count = count - parseInt(n / prod);
    }
     
    return count;
}
 
// Driver code
var n = 10;
 
document.write(countMultiples(n));
 
// This code is contributed by 29AjayKumar
 
</script>
Producción: 

8

 

Publicación traducida automáticamente

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