Numbers up to 100 divisible by 2, 3, or 5

Question

Consider the integers from 1 to 100. How many of them are divisible by 2, by 3, or by 5 (that is, by at least one of these)?

Accepted Answer

If we just add the three counts we double count numbers divisible by more than one. Inclusion-exclusion fixes this: add singles, subtract pairs, add the triple. Single counts (using \lfloor 100/d \rfloor): - divisible by 2: 50; by 3: 33; by 5: 20. Pair counts (divisible by the least common multiple): - by 6: 16; by 10: 10; by 15: 6. Triple count: - by 30: 3. Combine: 50 + 33 + 20 - 16 - 10 - 6 + 3 = 103 - 32 + 3 = 74. Takeaway. For "at least one of three," use A + B + C - AB - AC - BC + ABC. Here the answer is 74.

Numbers up to 100 divisible by 2, 3, or 5

Your answer

Discussion

Learn the concepts

Related questions