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 Mint 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 codeint 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 approachimport java.io.*;public class GFG{// Function to count the numbers that// are divisible by the numbers in// the array from range 1 to Mstatic 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 codepublic 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 lstlst = [ 2, 3, 5, 7 ]# Given number Mm = 100n = len(lst)# Function callprint(count(lst, m, n)) # This code is contributed by vishu2908 |
C#
// C# program for the above approachusing System;class GFG{// Function to count the numbers that// are divisible by the numbers in// the array from range 1 to Mstatic 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 codepublic 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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
