How many integers between 2001 and 3000 inclusive are not divisible by any of the three prime numbers 3, 7 and 13?

I approached by finding the number of integers between 1 and 3000 inclusive and the number of integers between 1 and 2000 inclusive, finding the difference between these and subtracting it from 1000 (the number of integers between 2001 and 3000 inclusive).

This gives me (all fractions have the floor function on them:

$$1000-(\frac{3000}{3}+\frac{3000}{7}+\frac{3000}{13}-\frac{3000}{3*7}-\frac{3000}{3*13}-\frac{3000}{7*13}+\frac{3000}{3*7*13}-(\frac{2000}{3}+\frac{2000}{7}+\frac{2000}{13}-\frac{2000}{3*7}-\frac{2000}{3*13}-\frac{2000}{7*13}+\frac{2000}{3*7*13}))$$

which gives me

$$1000-(1000+428+230-142-76-32+10-(666+285+153-95-51-21+7))= 526$$

Is this the correct, if so would this be the most efficient way to calculate it, if not, how would I go about performing this calculation?

Thanks

• Looks good to me, and it is how I would calculate it (although you need floor functions). – Michael Burr May 22 '19 at 10:08

This is correct, and is the most efficient way to calculate it for the numbers $$3,7,13$$. The final answer is correct also. Basically, inclusion-exclusion is the way to go if the range that you're checking (in this case $$2000$$ to $$3000$$) is "large" and the number of things that are not allowed to be multiples (in this case, $$3$$) is "small".