# Count of numbers upto M divisible by given Prime Numbers

Given an array **arr[]** of Prime Numbers and a number **M**, the task is to count the number of elements in the range **[1, M]** that are divisible by any of the given prime numbers.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:arr[] = {2, 3, 5, 7} M = 100Output:78Explanation:

In total there are 78 numbers that are divisible by either of 2 3 5 or 7.

Input:arr[] = {2, 5, 7, 11} M = 200Output:137Explanation:

In total there are 137 numbers that are divisible by either of 2 5 7 or 11.

**Naive Approach:** The idea is iterate over the range **[1, M]** and check if any of the array element is divides the element in the range **[1, M]** then count the element else check for the next number in the range.

Below is the implementation of the above approach:

## C++

`// 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

`// 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

`# 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#

`// 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` |

## Javascript

`<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>` |

**Output**

78

**Time Complexity:** O(N*M) **Auxiliary Space:** O(1) **Another Approach:** Another method to solve this problem is use Dynamic Programming and Seive. Mark all the numbers up to M that are divisible by any prime number in the array. Then count all the marked numbers and print it.