perfect factors from the prime factorization of a large number This is probably an easy question, but I don't know how to do it:
In the prime factorization of $30!$, how many perfect factors occur?
This is from a timed competition, any answers that take more than 3 minutes are not great.
Do I prime factorize every number from $1$ to $30$? That would be extremely slow.
I would like a hint in the right direction.
 A: Assuming the problem is talking about perfect numbers (although then it's unclear what "in the prime factorization" means) you only need to consider $6$ and $28$. All higher even perfect numbers have the form $2^{p-1} (2^p - 1)$ where $2^p - 1$ is a Mersenne prime and the next Mersenne prime is $3^5 - 1 = 31$ which doesn't divide $30!$. And since $6, 28 \le 30$ it's clear that they both divide. So the answer is $\boxed{2}$.
The question is a little ambiguous even beyond the perfect issue; if $k$ isn't prime it's unclear how to interpret the question of "how many times" $k$ occurs as a factor in another number.
If "perfect" means something else, the prime factorization of $n!$ is given by Legendre's formula
$$\nu_p(n!) = \sum_{k \ge 1} \left\lfloor \frac{n}{p^k} \right\rfloor$$
for the greatest power of $p$ dividing $n!$, and it would be just about doable to compute this by hand for $n = 30$ and all primes $\le 30$. From here you can answer whatever questions you want about the factors.
Among other things you can compute that
$$\nu_2(30!) = 15 + 7 + 3 + 1 = 26$$
$$\nu_3(30!) = 10 + 3 + 1 = 14$$
$$\nu_7(30!) = 4$$
which gives that the greatest powers $k$ such that $6^k$ or $28^k$ divide $30!$ are $14$ and $4$ respectively. I don't know if that's what's intended.
Overall it's not the best-written question and should have been test-solved.
