Learn / Library / Brainteasers

A rare toggle count

BrainteasersMedium

$100$ lockers numbered $1$ to $100$ start closed. For each $k$ from $1$ to $100$ , person $k$ toggles every locker whose number is a multiple of $k$ . How many lockers are toggled exactly $3$ times in total?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Which numbers have exactly $3$ divisors?

Solution

Locker $n$ is toggled once per divisor of $n$ , so we need numbers with exactly $3$ divisors.
An odd number of divisors means $n$ is a square, and $3$ divisors means $n = p^{2}$ for a prime $p$ , with divisors $1$ , $p$ and $p^{2}$ .
With $p^{2} \leq 100$ the primes are $2$ , $3$ , $5$ and $7$ , giving $4$ , $9$ , $25$ and $49$ .
So the number of such lockers is $4$ .

Answer: $4$

Next question Back to the library