Números que no son divisibles por ningún número en el rango [2, 10]

Dado un número entero N , la tarea es encontrar la cuenta de todos los números del 1 al N que no son divisibles por ningún número en el rango [2, 10] .

Ejemplos: 

Entrada: N = 12 
Salida: 2 
1, 11 son los únicos números en el rango [1, 12] que no son divisibles por ningún número del 2 al 10

Entrada: N = 20 
Salida: 5 

Enfoque: los números totales del 1 al n que no son divisibles por ningún número del 2 al 10 son iguales a n menos los números que son divisibles por algunos números del 2 al 10 .

El conjunto de los números que son divisibles por algunos números del 2 al 10 se puede encontrar como unión del conjunto de los números del 1 al n divisibles por 2 , el conjunto de los números divisibles por 3, y así hasta el 10 .

Tenga en cuenta que los conjuntos de números divisibles por 4 , 6 u 8 son subconjuntos del conjunto de números divisibles por 2 , y los conjuntos de números divisibles por 6 o 9 son subconjuntos del conjunto de números divisibles por 3 . Entonces no hay necesidad de unir 9 conjuntos, es suficiente unir conjuntos para 2, 3, 5 y 7 solamente.

El tamaño del conjunto de números del 1 an divisible por 2 , 3, 5 y 7 se puede calcular usando un principio de inclusión-exclusión que dice que se debe sumar el tamaño de cada conjunto individual, el tamaño de las intersecciones por pares debe ser restado, se debe sumar el tamaño de todas las intersecciones de tres conjuntos y así sucesivamente.

El tamaño del conjunto de números de 1 a n divisible por 2 es igual a ⌊n / 2⌋ , el tamaño del conjunto de números de 1 a n divisible por 2 y 3 es igual a ⌊n / (2 * 3) ⌋ y así sucesivamente.

Entonces, la fórmula es n – ⌊n / 2⌋ – ⌊n / 3⌋ – ⌊n / 5⌋ – ⌊n / 7⌋ + ⌊n / (2 * 3)] + ⌊n / (2 * 5)] + ⌊n / (2 * 7)] + ⌊n / (3 * 5)] + ⌊n / (3 * 7)] + ⌊n / (5 * 7)] – ⌊n / (2 * 3 * 5 )] – ⌊n / (2 * 3 * 7)] – ⌊n / (2 * 5 * 7)] – ⌊n / (3 * 5 * 7)]+ ⌊n / (2 * 3 * 5 * 7 )]

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of numbers
// from 1 to N which are not divisible by
// any number in the range [2, 10]
int countNumbers(int n)
{
    return n - n / 2 - n / 3 - n / 5 - n / 7
           + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35
           - n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
}
 
// Driver code
int main()
{
    int n = 20;
    cout << countNumbers(n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return the count of numbers
// from 1 to N which are not divisible by
// any number in the range [2, 10]
static int countNumbers(int n)
{
    return n - n / 2 - n / 3 - n / 5 - n / 7
        + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35
        - n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
}
 
// Driver code
public static void main (String[] args)
{
    int n = 20;
    System.out.println(countNumbers(n));
}
}
 
// This code is contributed by mits

# Python3 implementation of the approach
 
# Function to return the count of numbers
# from 1 to N which are not divisible by
# any number in the range [2, 10]
def countNumbers(n):
    return (n - n // 2 - n // 3 - n // 5 - n // 7 +
             n // 6 + n // 10 + n // 14 + n // 15 +
             n // 21 + n // 35 - n // 30 - n // 42 -
             n // 70 - n // 105 + n // 210)
 
# Driver code
if __name__ == '__main__':
    n = 20
    print(countNumbers(n))
 
# This code contributed by Rajput-Ji

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the count of numbers
// from 1 to N which are not divisible by
// any number in the range [2, 10]
static int countNumbers(int n)
{
    return n - n / 2 - n / 3 - n / 5 - n / 7
        + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35
        - n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
}
 
// Driver code
static void Main()
{
    int n = 20;
    Console.WriteLine(countNumbers(n));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation of the approach
 
// Function to return the count of numbers
// from 1 to N which are not divisible by
// any number in the range [2, 10]
function countNumbers($n)
{
    return (int)($n - $n / 2) - (int)($n / 3 ) -
           (int)($n / 5 ) - (int)($n / 7) +
           (int)($n / 6 ) + (int)($n / 10) +
           (int)($n / 14) + (int)($n / 15) +
           (int)($n / 21) + (int)($n / 35) -
           (int)($n / 30) - (int)($n / 42) -
           (int)($n / 70) - (int)($n / 105) +
           (int)($n / 210);
}
 
// Driver code
$n = 20;
echo(countNumbers($n));
 
// This code is contributed by Code_Mech.
?>

<script>
 
// Javascript implementation of the approach
 
// Function to return the count of numbers
// from 1 to N which are not divisible by
// any number in the range [2, 10]
function countNumbers(n)
{
    return n - parseInt(n / 2, 10) - parseInt(n / 3, 10) -
               parseInt(n / 5, 10) - parseInt(n / 7, 10) +
               parseInt(n / 6, 10) + parseInt(n / 10, 10) +
               parseInt(n / 14, 10) + parseInt(n / 15, 10) +
               parseInt(n / 21, 10) + parseInt(n / 35, 10) -
               parseInt(n / 30, 10) - parseInt(n / 42, 10) -
               parseInt(n / 70, 10) - parseInt(n / 105, 10) +
               parseInt(n / 210, 10);
}
 
// Driver code
let n = 20;
 
document.write(countNumbers(n));
 
// This code is contributed by mukesh07
 
</script>

5

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)