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:
Input: arr[] = {2, 3, 5, 7} M = 100
Output: 78
Explanation:
In total there are 78 numbers that are divisible by either of 2 3 5 or 7.Input: arr[] = {2, 5, 7, 11} M = 200
Output: 137
Explanation:
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 import java.io.*; public 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> |
78
Time Complexity: O(N*M)
Auxiliary Space: O(1)
Another Approach: Another method to solve this problem is use Dynamic Programming and Sieve. 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.