9A. Counting Multiples in a Range (Divisibility-Based Counting)

A recurring question format asks “how many numbers between A and B are divisible by d” or combinations thereof using inclusion-exclusion. The core formula:

Number of multiples of d from 1 to N = ⌊ (N)/(d) ⌋

For a range [A,B] (inclusive), the count of multiples of d is ⌊ (B)/(d) ⌋ - ⌊ (A-1)/(d) ⌋.

Example 1: How many numbers between 1 and 300 (inclusive) are divisible by 9? ⌊300/9⌋ = 33 (since 9×33=297≤300<9×34=306). 33 numbers.

Example 2: How many numbers between 100 and 300 (inclusive) are divisible by 7? ⌊300/7⌋=42, ⌊99/7⌋=14. Count =42-14=28.

Example 3 (inclusion-exclusion, revisited from Section 9): How many numbers from 1 to 500 are divisible by 3 or 5? As shown earlier, the answer is 233, using ⌊500/3⌋+⌊500/5⌋-⌊500/15⌋ = 166+100-33.

Example 4: How many numbers from 1 to 200 are divisible by 3 but NOT by 5? (Divisible by 3) − (divisible by both 3 and 5, i.e., by 15) = ⌊200/3⌋ - ⌊200/15⌋ = 66 - 13 = 53.

Example 5: How many numbers from 1 to 300 are divisible by 13? ⌊300/13⌋=23 (since 13×23=299≤300<13×24=312). 23 numbers.

Example 6 (a “divisible by one, not the other” edge case with a shared factor): How many numbers from 1 to 1,000 are divisible by 6 but NOT by 12? (Divisible by 6) − (divisible by both 6 and 12, which — since 12 is already a multiple of 6 — is simply divisible by 12) = ⌊1000/6⌋ - ⌊1000/12⌋ = 166-83=83. 83 numbers. This variant is a useful trap-check: whenever the “other” divisor is already a multiple of the first, “divisible by both” collapses to “divisible by the larger one” — no separate LCM computation is needed.