Recuento de números hasta M divisible por números primos dados

Dada una array arr[] de números primos y un número M , la tarea es contar el número de elementos en el rango [1, M] que son divisibles por cualquiera de los números primos dados.
 

Ejemplos:

Entrada: arr[] = {2, 3, 5, 7} M = 100  
Salida: 78  
Explicación:
En total hay 78 números que son divisibles por 2 3 5 o 7.

Entrada: arr[] = {2, 5, 7, 11} M = 200
Salida: 137
Explicación:
En total hay 137 números que son divisibles por 2 5 7 o 11.

Enfoque ingenuo: la idea es iterar sobre el rango [1, M] y verificar si alguno de los elementos de la array divide el elemento en el rango [1, M] y luego contar el elemento; de lo contrario, verificar el siguiente número en el rango.
A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to count the numbers that
// are divisible by the numbers in
// the array from range 1 to M
int count(int a[], int M, int N)
{
    // Initialize the count variable
    int cnt = 0;
 
    // Iterate over [1, M]
    for (int i = 1; i <= M; i++) {
 
        // Iterate over array elements arr[]
        for (int j = 0; j < N; j++) {
 
            // Check if i is divisible by a[j]
            if (i % a[j] == 0) {
 
                // Increment the count
                cnt++;
                break;
            }
        }
    }
 
    // Return the answer
    return cnt;
}
 
// Driver code
int main()
{
    // Given array arr[]
    int arr[] = { 2, 3, 5, 7 };
 
    // Given Number M
    int m = 100;
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << count(arr, m, n);
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to count the numbers that
// are divisible by the numbers in
// the array from range 1 to M
static int count(int a[], int M, int N)
{
     
    // Initialize the count variable
    int cnt = 0;
 
    // Iterate over [1, M]
    for(int i = 1; i <= M; i++)
    {
         
        // Iterate over array elements arr[]
        for(int j = 0; j < N; j++)
        {
             
            // Check if i is divisible by a[j]
            if (i % a[j] == 0)
            {
                 
                // Increment the count
                cnt++;
                break;
            }
        }
    }
     
    // Return the answer
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given array arr[]
    int arr[] = { 2, 3, 5, 7 };
 
    // Given number M
    int m = 100;
    int n = arr.length;
 
    // Function call
    System.out.print(count(arr, m, n));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to count the numbers that
# are divisible by the numbers in
# the array from range 1 to M
def count(a, M, N):
     
    # Initialize the count variable
    cnt = 0
 
    # Iterate over [1, M]
    for i in range(1, M + 1):
 
        # Iterate over array elements arr[]
        for j in range(N):
 
            # Check if i is divisible by a[j]
            if (i % a[j] == 0):
 
                # Increment the count
                cnt += 1
                break
 
    # Return the answer
    return cnt
 
# Driver code
 
# Given list lst
lst = [ 2, 3, 5, 7 ]
 
# Given number M
m = 100
n = len(lst)
 
# Function call
print(count(lst, m, n))
 
# This code is contributed by vishu2908   

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count the numbers that
// are divisible by the numbers in
// the array from range 1 to M
static int count(int []a, int M, int N)
{
     
    // Initialize the count variable
    int cnt = 0;
 
    // Iterate over [1, M]
    for(int i = 1; i <= M; i++)
    {
         
        // Iterate over array elements []arr
        for(int j = 0; j < N; j++)
        {
             
            // Check if i is divisible by a[j]
            if (i % a[j] == 0)
            {
                 
                // Increment the count
                cnt++;
                break;
            }
        }
    }
     
    // Return the answer
    return cnt;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 2, 3, 5, 7 };
 
    // Given number M
    int m = 100;
    int n = arr.Length;
 
    // Function call
    Console.Write(count(arr, m, n));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
    // Javascript program for the above approach
     
    // Function to count the numbers that
    // are divisible by the numbers in
    // the array from range 1 to M
    function count(a, M, N)
    {
        // Initialize the count variable
        let cnt = 0;
 
        // Iterate over [1, M]
        for (let i = 1; i <= M; i++) {
 
            // Iterate over array elements arr[]
            for (let j = 0; j < N; j++) {
 
                // Check if i is divisible by a[j]
                if (i % a[j] == 0) {
 
                    // Increment the count
                    cnt++;
                    break;
                }
            }
        }
 
        // Return the answer
        return cnt;
    }
     
    // Given array arr[]
    let arr = [ 2, 3, 5, 7 ];
   
    // Given Number M
    let m = 100;
    let n = arr.length;
   
    // Function Call
    document.write(count(arr, m, n));
     
</script>

78

Complejidad de tiempo: O(N*M) 
Espacio auxiliar: O(1) 
Otro enfoque: Otro método para resolver este problema es usar programación dinámica y tamiz . Marque todos los números hasta M que sean divisibles por cualquier número primo en la array. Luego cuenta todos los números marcados e imprímelo.