For arbitrary bases I think this should do what you want.
factorialZeros[n_Integer, b_Integer] /; n > 1 && b > 1 :=
Module[{pfacs, pexpons},
{pfacs, pexpons} = Transpose[FactorInteger[b]];
Min[Floor[
Map[Sum[Floor[n/#^j], {j, Floor[Log[#, n]]}] &, pfacs]/pexpons]]
]
For example:
In[86]:= factorialZeros[243, 12]
(* Out[86]= 118 *)
