Compute largest integer power of $6$ that divides $73!$

Question

I am looking to compute the largest integer power of $6$ that divides $73!$

If it was something smaller, like $6!$ or even $7!$, I could just use trial division on powers of $6$. However, $73!$ has $106$ decimal digits, and thus trial division isn't optimal.

Is there a smarter way to approach this problem?

Answer 1

HINT: There are $\lfloor73/3\rfloor=24$ numbers divisible by 3, $\lfloor73/9\rfloor=8$, numbers divisible by 9, $\lfloor73/27\rfloor=2$ numbers divisible by 27 in the set $[1,73]\cap\mathbb{N}$. It should be easy now to obtain that the answer is 34 (with the value $6^{34}$).

Answer 2

Hint: $6 = 2 \cdot 3$. Since $3$ is less frequent than $2$ in the product $73! = 1 \cdot 2 \cdots 73$, count the number of factors of $3$ in the numbers $1$, $2$, $\ldots$, $73$. Note that some numbers give you more than one factor of $3$.