Counting Numbers Divisible by Given Primes | Geeks for Geeks

When I first stumbled upon the problem “Count how many numbers from 1 to M are divisible by any number from a given set of primes”, it looked deceptively simple.

The statement in my head was straightforward:

• Input: a set of primes arr, and a number m.

• Task: count how many numbers between 1 and m are divisible by at least one of the primes in arr.

Let’s solve the given problem…

First Attempt - Brute Force Check

Like any beginner would, I started with the most natural idea:
For each number i from 1 to m, check if it is divisible by any prime in the list.

If divisible → increase count and break (no need to check further primes for that i).

Here’s the code I wrote:

class Solution:
    def countDivisible(self, arr, m):
        count = 0
        for i in range(1, m+1):
            for p in arr:
                if i % p == 0:
                    count += 1
                    break
        return count

This worked well for smaller test cases.
But when m was very large (say 10^7 or more), this solution got TLE.

In fact, it solved 1010/1120 test cases before failing.
And that’s when I realized brute force would never scale here.

Second Attempt - Marking Multiples

Next, I thought: “Why check every number individually? Why not directly mark multiples of primes?”

So I created a Boolean array divisible[] of size m+1, initialized to False.

• For each prime p, I marked all its multiples as True.

• Finally, I summed up the Boolean array to count how many were divisible.

Here’s the code I wrote:

class Solution:
    def countDivisible(self, arr, m):
        divisible = [False] * (m+1)
        for p in arr:
            for multiple in range(p, m+1, p):
                divisible[multiple] = True
        return sum(divisible[1:])

This was significantly faster!

• Instead of checking each number with every prime, I just walked through multiples.

• Complexity dropped to about O(m/p1 + m/p2 + …) which is much better than O(m * len(arr)).

But still, it failed on very large values of m.
I got 1110/1120 test cases correct.

Third Attempt - Inclusion-Exclusion Principle

At this point, brute force ideas were exhausted. So I looked deeper into mathematics.

The real trick here is the Inclusion-Exclusion Principle (IEP).
Instead of simulating the divisibility, we can mathematically count directly:

1. For each subset of primes, calculate the LCM of that subset.

2. Count how many numbers up to m are divisible by that LCM (m // lcm).

3. If the subset size is odd → add this count.
   If even → subtract this count.

This ensures we don’t double-count numbers that are divisible by multiple primes.

Code for Inclusion-Exclusion: With the help of GPT

from math import gcd

class Solution:
    def countDivisible(self, arr, m):
        n = len(arr)

        def lcm(a, b):
            return a * b // gcd(a, b)

        count = 0

        # Iterate through all subsets
        for mask in range(1, 1 << n):
            subset_lcm = 1
            bits = 0
            for i in range(n):
                if mask & (1 << i):
                    bits += 1
                    subset_lcm = lcm(subset_lcm, arr[i])
                    if subset_lcm > m:   # Too large, no contribution
                        break
            else:
                contrib = m // subset_lcm
                if bits % 2 == 1:   # odd subset → add
                    count += contrib
                else:               # even subset → subtract
                    count -= contrib

        return count

This method passed all test cases (1120/1120).
It is mathematically elegant and extremely efficient compared to brute force.

Complexity Analysis

• Approach 1 (Brute Force):

  • Time: O(m * n)

  • Space: O(1)

  • Failed for large m.

• Approach 2 (Marking Multiples):

  • Time: O(m/p1 + m/p2 + …) ≈ O(m log m) in worst case.

  • Space: O(m)

  • Faster, but memory heavy for very large m.

• Approach 3 (Inclusion-Exclusion):

  • Time: O(2^n * n * log m) (since we calculate LCMs for all subsets).

  • Space: O(1)

  • Works best when n (number of primes) is small (≤ 15).

  • Scales beautifully for large m (like 10^12).

Final Thoughts

This problem was a beautiful journey for me:

• I started with brute force (got partial AC).

• Then I tried a sieve-like marking approach (almost solved).

• Finally, with the help of AI and a bit of math, I discovered the Inclusion-Exclusion Principle which cracked the problem fully.

Lesson Learned: Sometimes brute force intuition takes you part of the way, but true optimization comes from stepping back and looking at the mathematical structure of the problem.