How to solve this problem

Question

Find the number of numbers between $100$ to $400$ which are divisible by either $2,3,5,7$ Please give some shortcut or some easy way

Answer 1

The question is basically just a sieve, similar to looking for primes.

The period that visits all combinations of said numbers is long ($2\times 3\times 5 \times 7=210$) so whatever you do, it won't be much quicker than the brute method.

For instance, starting with 2 and 5, you have the ones that are NOT divisible by any of them like this:

[201,203,207,209],211,213,217,219,...

You can just repeat this pattern of 4.

When you start again for 3 and only keep those that aren't divisible by it, the pattern repeats each 2*3*5=30 numbers, but only 8 candidates are left in each period:

[203,209,211,217,221,223,227,229],233,239,...

So the next step, when you test for divisibility of 7, you have less work to do (but as said, not much less). What remains are the numbers that are not divisible by any of them. The rest are solutions to your problem.

Answer 2

It should be clear to figure out how many even numbers there are between $100$ and $400$. If you can't see it immediately, consider the amount of even numbers between $0$ and, say, $20$ and draw some conclusions from that.

Then note that $400-100=300$.. This should give a good indicator of the number of numbers divisible by $3$ and $5$.

I'll let you figure $7$ out.

As noted by Steven, this method double, triple and quadruple counts so you also need to count how many times products of these numbers appear as well.

There is, what I think, a better way. By the fundamental theorem of arithmetic, every positive integer can be uniquely decomposed as a product of prime numbers. Another fact (which you may or may not know but it's not hard to see, at least at an intuitive level) is that the largest prime that can divide a given positive integer $N$ is less than or equal to $\sqrt{N}$. In this case, our upper bound is $400$ so we want to look at all primes less than or equal to $\sqrt{400} = 20$. The primes satisfying this are $2,3,5,7,11,13,17,19$. We want to calculate the number that are divisible by $2,3,5,7$. This is equivalent to finding the numbers that are divisible by $11,13,17,19$ but not $2,3,5,7$. If you invoke the fundamental theorem of arithmetic, this problem becomes very easy at this point.