Consider the set of integers {1, 2, 3, ..., 5000}. The number of integers that is divisible by neither 3 nor 4 is:

A. 1...

Question

Consider the set of integers {1, 2, 3, ..., 5000}. The number of integers that is divisible by neither 3 nor 4 is:

A. 1668  B. 2084  C. 2500  D. 2016

Accepted Answer

2500 integers in {1,...,5000} are divisible by neither 3 nor 4. We want integers from 1 to 5000 that avoid both 3 and 4 as factors. Using inclusion-exclusion, we count those divisible by 3 or 4 (or both), then subtract from 5000. The overlap — divisible by both 3 and 4 — is the same as divisible by lcm(3,4) = 12, so we avoid double-counting.