Primes and Factorization

To list the primes up to $60$, write out $2, \ldots, 60$ and strike the proper multiples of $2$, then of $3$, $5$ and $7$. Then stop: $\sqrt{60} < 8$, so every composite number up to $60$ has a prime factor of at most $7$ and is already struck. What survives are the $17$ primes $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59$.

If $221 = ab$ with $1 < a \le b$, then $a \le \sqrt{221} < 15$ (as $15^2 = 225$). So only the primes $2, 3, 5, 7, 11, 13$ need testing. $221$ is odd, its digit sum $5$ is not a multiple of $3$, and it does not end in $0$ or $5$; $221 = 7\cdot31 + 4$ and $221 = 11\cdot20 + 1$; but $221 = 13\cdot17$. Composite.

Is $391$ prime? Here $19^2 = 361 < 391 < 400 = 20^2$, so test the primes up to $19$. The small ones fail at a glance; $391 = 7\cdot55 + 6$, $391 = 11\cdot35 + 6$, $391 = 13\cdot30 + 1$; and then $391 = 17\cdot23$. The factor appears only at $17$ — stopping the search early at $13$ would have wrongly declared $391$ prime.

Factor $5040$. Divide by the smallest prime as long as it goes in: $5040 \to 2520 \to 1260 \to 630 \to 315$ uses four $2$s; $315 \to 105 \to 35$ uses two $3$s; and $35 = 5\cdot7$. So $5040 = 2^4\cdot3^2\cdot5\cdot7$. Working upward from the smallest prime guarantees nothing is missed: once the $2$s are gone, no later quotient is even.

$200 = 2^3\cdot5^2$. By uniqueness, a divisor of $200$ can contain no prime but $2$ and $5$, and no more of each than $200$ has, so it is $2^i5^j$ with $0 \le i \le 3$ and $0 \le j \le 2$. That is $4$ choices times $3$ choices: $\tau(200) = 12$ divisors, laid out as a grid in which moving right multiplies by $2$ and moving up multiplies by $5$.

Find the smallest positive $k$ with $540k$ a perfect square. Factor: $540 = 2^2\cdot3^3\cdot5$. A square needs every exponent even; $2^2$ already is, $3^3$ needs one more $3$, and $5^1$ needs one more $5$. So $k = 3\cdot5 = 15$, and indeed $540\cdot15 = 8100 = 90^2$. Any smaller $k$ leaves an odd exponent somewhere.

Stack one dot above each $k = 1, \ldots, 10$ for each factor $2$ in $k$. Counting by rows: the bottom row has a dot at every even $k$, $\lfloor 10/2 \rfloor = 5$ of them; the second row at the multiples of $4$, $\lfloor 10/4 \rfloor = 2$; the third at the multiples of $8$, $\lfloor 10/8 \rfloor = 1$. Total $5 + 2 + 1 = 8$, so $2^8$ exactly divides $10! = 3628800$.

Each trailing zero is a factor $10 = 2\cdot5$, and $n!$ has far more $2$s than $5$s, so the $5$s decide. Exponent of $5$ in $100!$: $\lfloor100/5\rfloor + \lfloor100/25\rfloor = 20 + 4 = 24$ (and $125 > 100$ stops the sum). So $100!$ ends in $24$ zeros.

Find the largest $k$ with $12^k \mid 30!$. Since $12^k = 2^{2k}3^k$, both primes limit $k$. Exponent of $2$ in $30!$: $15 + 7 + 3 + 1 = 26$, so $2k \le 26$ and $k \le 13$. Exponent of $3$: $10 + 3 + 1 = 14$, so $k \le 14$. The tighter bound wins: $k = 13$. Note that the scarcer prime here is $2$, because $12$ needs two of them at a time.