Find numbers that are not divisible by any number in a range, using C++

In this article, we will discuss the problem of finding numbers between 1 and n (given) that are not divisible by any number between 2 and 10. Let us 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.

Methods to solve

Easy method

If we check every number from 1 to num, whether it can be solved Any number between 2 and 10 is divisible. If not, then increment the count. But this method takes too much time, thus increasing the time complexity.

Efficient method

The best way we can think of is to first find the numbers from 1 to num, which can be any number in the range [2, 10], and then subtract from num Go count this.

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

We need to find all numbers that are divisible by 2, 3, and 5. , and 7. We can calculate it based on the inclusion-exclusion principle.

Inclusion-Exclusion Principle

It states that we should include the size of each individual set, you should remove the size of the pairwise intersection, add the sizes of all intersections of the three groups, and so on .

The 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 ways to find numbers that are not divisible between 2 and n. To solve this problem, we discuss the inclusion-exclusion principle. We also discuss C programs to apply this method to obtain results in O(1) complexity. You can write this program in any other language like Java, C, Python, etc. We hope this article was helpful to you.

The above is the detailed content of Find numbers that are not divisible by any number in a range, using C++. For more information, please follow other related articles on the PHP Chinese website!