Find Numbers Not Divisible by Any in Range Using C++

In this article, we will discuss the problem to find the numbers from 1 to n(given) which are can not be divided by any number from 2 to 10. Let's understand this with some examples −

Input : num = 14
Output : 3
Explanation: There are three numbers, 1, 11, and 13, which are not divisible.

Input : num = 21
Output : 5
Explanation: There are five numbers 1, 11, 13, 17, and 19, which are not divisible.

Approach to find The Solution

Simple Approach

If we check every number from 1 to num, whether it can be divided by any number from 2 to 10. If no, then increment the count. But this approach will take too much time hence increasing the time complexity.

Efficient Approach

The best approach we can think of is first to find the numbers from 1 to num, divisible by any number in the range [ 2, 10 ], then subtract this count with num.

So first, we need to find all the numbers divisible by 2, 3, 4, 5,10. But numbers divisible by 4, 6, 8, and 10 are divisible by 2, and numbers divisible by three are divisible by 6 and 9.

We need to find all the numbers divisible by 2, 3, 5, and 7. And this we can calculate from the inclusion-exclusion principle.

Inclusion-exclusion Principle

It states that we should include every single set's size, you should remove pairwise intersection's size, all intersection's size of three sets should be added, and so on.

Formula to find all numbers is,

= NUM – X + Y – Z + A.

Where,

X = num divisible by 2, 3, 5, 7 ( [num / 2] + [num / 3] + [num / 5] + [num / 7] )

Y = num divisible by (2,3), (2, 5), (2, 7), (3, 5), (3, 5), (3, 7) and (5, 7) = ( [num / (2 * 3)] + [num / (2 * 5)] + [num / (2 * 7)] + [num / (3 * 5)] + num / (3 * 7)] + [num / (5 * 7)] ).

Z = num divisible by (2, 3, 5), (2, 3, 7), (2, 5, 7) and (3, 5, 7) = ( [num / (2 * 3 * 5)] + [num / (2 * 3 * 7)] + [num / (2 * 5 * 7)] + [num / (3 * 5 * 7)] )

A = num divisible by (2, 3, 5, 7) = ( [num / (2 * 3 * 5 * 7)] )

Example

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 21, result;
   // applying formula from inclusion - exclusion principle
   // to find the count of numbers not divisible by any number from 2 to 10.
   result = n - n / 2 - n / 3 - n / 5 - n / 7
      + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35
      - n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
   cout << "The count of numbers, not div by [2, 10] is: " << result;

   return 0;
}

Output

The count of numbers, not div by [2, 10] is: 5

Conclusion

In this article, we discussed the way to find non-divisible numbers from 2 to n. To solve this problem, we discussed the inclusion-exclusion principle. We also discussed the C++ program to apply the approach to get the result with O(1) complexity. You can write this program in any other language like Java, C, Python, etc. We hope you find this article helpful.