[Question]
  [
Related: [Zeroes at the end of a factorial](https://codegolf.stackexchange.com/questions/79762/zeroes-at-the-end-of-a-factorial)
Today, we are going to calculate how many zeroes are there at the end of \$n!\$ (the factorial of \$n\$) in base \$m\$.
Or in other words: For given integers \$n\$, and, \$m\$. Calculate the integer \$p\$ which is the highest power of \$m\$ dividing \$n!\$: \$p \in \mathbb{N}\_0\$ which holds \$ \left( m^p \mid n! \right) \land \left( m^{p+1} \nmid n! \right) \$. Here, \$n!\$ is the factorial of \$n\$ which equals to the product of all positive integers less than or equal to \$n\$. The value of \$0!\$ is \$1\$.
## Input / Output
* Two integers \$n\$, \$m\$.
* One integer: How many zeroes at end of \$n!\$ in base \$m\$.
## Rules
* As [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), the shortest codes in bytes win.
* Your program is required to support \$0\le n\le 1{,}000{,}000\$; \$2\le m\le 1{,}000\$ at least. The program should be able to output correct results for any inputs in above range with reasonable resource (typically, <1 minutes on a normal laptop).
* As this question is only talking about integers. No floating point errors may allowed in your output. You may, however, output 3.0 when 3 is required. But 2.9999999999999996 is certainly not allowed.
## Testcases
```
      n,    m -> output
      0,    2 -> 0
      1,    2 -> 0
      2,    2 -> 1
      3,    2 -> 1
      4,    2 -> 3
      9,    6 -> 4
     10,  100 -> 1
     80,  100 -> 9
      4,    8 -> 1
     15,   12 -> 5
     16,   12 -> 6
     39,   45 -> 8
    100,    2 -> 97
    100,    3 -> 48
    100,    4 -> 48
    100,    5 -> 24
    100,    6 -> 48
    100,    7 -> 16
    100,    8 -> 32
    100,    9 -> 24
    100,   10 -> 24
    100,   13 -> 7
    100,   36 -> 24
    100,   42 -> 16
    100,   97 -> 1
    100,  100 -> 12
1000000,    2 -> 999993
1000000,    3 -> 499993
1000000,    4 -> 499996
1000000,    6 -> 499993
1000000,    7 -> 166664
1000000,    8 -> 333331
1000000,    9 -> 249996
1000000,  999 -> 27776
1000000, 1000 -> 83332
```
Above \$n\$ is written in base 10. You are allowed to receive \$n\$ as an array of integers in base \$m\$ if you want.
## Related OEIS
It is interesting that this question involve at least 14 sequences on OEIS. Maybe you can find out some helpful formula to solve this problem on it.
OEIS includes sequences for every \$2 \le m \le 16\$:
* 2: [A011371](https://oeis.org/A011371)
* 3, 6: [A054861](https://oeis.org/A054861)
* 4: [A090616](https://oeis.org/A090616)
* 5, 10, 15: [A027868](https://oeis.org/A027868)
* 7, 14: [A054896](https://oeis.org/A054896)
* 8: [A090617](https://oeis.org/A090617)
* 9: [A090618](https://oeis.org/A090618)
* 11: [A064458](https://oeis.org/A064458)
* 12: [A090619](https://oeis.org/A090619)
* 13: [A090620](https://oeis.org/A090620)
* 16: [A090621](https://oeis.org/A090621)
Also, by treating above sequences as a matrix, there are other related sequences:
* [A090622](https://oeis.org/A090622): Square array read by antidiagonals of highest power of k dividing n! (with n,k>1).
* [A098094](https://oeis.org/A098094): T(n,k) = greatest e such that k^e divides n!, 2<=k<=n (triangle read by rows).
* [A011776](https://oeis.org/A011776): a(1) = 1; for n > 1, a(n) is defined by the property that n^a(n) divides n! but n^(a(n)+1) does not.
  
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 22 bytes
```
#!~IntegerExponent~#2&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n277X1mxzjOvJDU9tci1oiA/LzWvpE7ZSO1/QFFmXomCQ3q0oQEY6BjH/v8PAA "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 12 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
Æfµ⁹ọ€S:ċⱮ`Ṃ
```
A dyadic Link accepting the base, \$m\$, on the left and the factorial-input, \$n\$, on the right that yields the number of trailing zeros of \$n!\_{m}\$ as an integer.
**[Try it online!](https://tio.run/##ASkA1v9qZWxsef//w4ZmwrXigbnhu43igqxTOsSL4rGuYOG5gv///zM2/zEwMA "Jelly – Try It Online")**
### How?
```
Æfµ⁹ọ€S:ċⱮ`Ṃ - Link: integer, m; integer, n   e.g. 72 100
Æf           - prime factorisation (m)             [ 2, 2, 2, 3, 3]
  µ          - start a new monadic chain - f(x=that)
   ⁹ €       - for each i in [1..n]:
    ọ        -   (i) order (vectorised across x)
                                                   [[0,0,0,0,0],[1,1,1,0,0],[0,0,0,1,1],[2,2,2,0,0],...]
      S      - sum (vectorises)                    [97,97,97,48,48]
          `  - use x as both arguments of:
         Ɱ   -   map across (x) with:
        ċ    -     count occurrences               [ 3, 3, 3, 2, 2]
       :     - integer divide                      [32,32,32,24,24]
           Ṃ - minimum                             24
```
[Answer]
# [Python 2](https://docs.python.org/2/), ~~133~~ 130 bytes
Saved **3 bytes** thanks to kops!
```
n,m=input()
f=()
i=2
k=lambda n,p:n and n/p+k(n/p,p)
exec"while m%i<1:m/=i;f+=i,\ni+=1\n"*m
print min(k(n,p)/f.count(p)for p in f)
```
[Try it online!](https://tio.run/##DctBCoMwEADAe16xCIWkhqYKvdjuT7xYTXDRbBaJtH19msvcRn55TdyXwjYisZxZGxWwQtirDfcpvpcJ2MrAMPEC7KTddNWKUf7r5@az0u4hXujVDdEhPUOLZEemFruRm2tUchBniMS6zvpcuM3p5KzFhHSAADEEU4p@2O5u/g "Python 2 – Try It Online")
Creates a list of all the prime factors of `m`. The program then computes the highest power of each prime factor that divides `n!` using the `lambda` function `k`. This number is divided by the number of times the prime factor is found in `f`. Finally, the program prints out the `min` of these values.
A math.stackexchange.com question with answers explaining how this works:
<https://math.stackexchange.com/questions/391067/power-of-a-number-in-a-factorial>
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 49 bytes
```
ＮθＮηＷ¬⁼ηΠυ⊞υ§Φ…·²η¬﹪÷η∨Πυ¹κ⁰Ｉ⌊Ｅυ÷↨Ｅ↨θι↨…↨θιμι¹№υι
```
[Try it online!](https://tio.run/##VU5NTwMhEL33V3AcEkxarz3pqske2m78B8gSmchCF5it/nocuFTfYb7fe2OcTiZqX@sYrlTOtHzYBKs87v72jvubQ28FnGOB15W0z@CUmFKcyRQgyRATZQekxFMZw2y/4Q19YfYYjKeMm33X4dPCoxJOKtGETsz2kQ/KC2442yZ5SXBXVeIgOXzJFveS35gShgKDzszGgAstcNLX5npXedbZ9mkvViWQ2b0efoy3g4v/V4tsuZspMURiA@qTjmOth33HruX6sPlf "Charcoal – Try It Online") Link is to verbose version of code. Explanation:
```
ＮθＮη
```
Input `n` and `m`.
```
Ｗ¬⁼ηΠυ⊞υ§Φ…·²η¬﹪÷η∨Πυ¹κ⁰
```
Find `m`'s prime factors.
```
  Ｅυ                    Map over prime factors
       ↨θι              Convert `n` to base `p`
      Ｅ    …↨θιμ        All prefixes
          ↨     ι       Converted from base `p`
     ↨           ¹      Take the sum
    ÷                   Integer divided by
                  №υι   Frequency of prime factor
 ⌊                      Take the minimum
Ｉ                       Cast to string
                        Implicitly print
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 13 bytes
```
ÆFZọ€Ḣ}S:ʋ@ẎṂ
```
[Try it online!](https://tio.run/##y0rNyan8//9wm1vUw929j5rWPNyxqDbY6lS3w8NdfQ93Nv0/vNxBHygc@f9/tIGOglGsjkK0IZQ2gtLGUNoEJg9UaGhgAGJaIJhAWQuwrBlQCKLPUkfBxBSiA242iGUMZ5nAWQh1ZnCWOZxlAWdZwlmGBggmwkRjhHYThI2W5kjaYPpAAOE1E4tYAA "Jelly – Try It Online")
After the `4, 48` fix it's too slow to run all of the test cases in one go, but I think it can still [handle them all individually](https://tio.run/##y0rNyan8//9wm1vUw929j5rWPNyxqDbY6lS3w8NdfQ93Nv0/vNxBHygc@f9/tIGOglGsjkK0IZQ2gtLGUNoEJg9UaGhgAGJaIJhAWQuwrBlQCKLPUkfBxBSiA242iGUMZ5nAWQh1ZnCWOZxlAWdZwlmGBggmwkRjhHYThI2W5kjaYPpAAOE1E4tYAA).
I'm not sure why `ɓ` (or `ð` for that matter) refuses to work here.
Takes \$m\$ on the left and \$n\$ on the right.
```
ÆF               Factor m into [prime, exponent] pairs.
  Z              Zip.
         ʋ@      With [[primes], [exponents]] as the right argument:
    €            For each integer in [1 .. n],
   ọ             how many times is it divisible by
     Ḣ}          each prime? (the list of which is popped from the pair)
       S         Sum the divisibilities,
        :        and floor-divide the sums by the exponents.
           Ẏ     Dump inner lists (not entirely sure why they're singletons),
            Ṃ    and return the minimum.
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~242~~ 237 bytes
* Saved five bytes thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat).
```
f(n,b){int*p=malloc(12*b),d=2,k,l;for(;b/d;++d){for(k=b;k%d<1;k/=d)p[d]++;for(k=2;p[d]&&k<d;p[d]*=d%k++>0);}for(k=0;n/++k;)for(d=2;k/d&&b/d;++d)for(l=k;p[d]&&l%d<1;l/=d)++p[b-~d];for(n=d=0;b/++d;k&&n<1|k/p[d]<n?n=k/p[d]:0)k=p[b-~d];d=n;}
```
[Try it online!](https://tio.run/##dZDPbsIwDMbve4pqE6Uh3kjS0NKFbC/BYRLjQBuYUEpA026MvTpzKH9Kxnyo@vtsf45dPX5U1X6/SByUZLt0X72NXs3qel0lXPRKAkYLsFCrxfozUWXfKEoN2XqyulS2Y0Zc2b42ZDMxU0pVkxHKYxzbkTn89bTpWEpfGFG7poIp16fUKuIRh6CJiePTAC/W2h5d6sOU2k@hdDMpH3/M9DDIaYNGJRoZZePYjfi37fuekXt1uvl9ZsTqU5PRTu32D2a@WLp5NPZbQ0U2n7j4IrnvVJHTHROV@Hl399BcRevqtfvUfe6@dcGzusPqaDVbuoRE27sIY5wwEMDIEXgbBAI/QdoGiZCeoIAM5NmAAWfsUjlsuLh0Di9JPgAuYHDGzGN2nliAHMDw4uxfWuRtTkFe5WXAAxCyzVmQz4FnbR5CKtpcBP24XSCkcP2gLCiQIhhR5K392fFa7aE@/KI@0lDHhW/qstGzUM/@qfeLY8hQxwP44KHuD3HLHzUQeZ7/SfCDG1rharv9Lw "C (gcc) – Try It Online")
---
# Annotated version
```
f(n,b){
 int*p=malloc(12*b) /* Since `b>=2` holds,
                           `12*b>=8*b+8==2*4*(b+1)==2*(b+1)*sizeof(int)`.
                       The pointer `p` represents two sparse arrays of
                       length `b+1` only indexed by primes, the first
                       storing the base's prime factorization.
                       Its latter half's `b+1` elements stores how many of
                       `k`'s (where `1<=k<=n`) prime factors with
                       multiplicities. */
 ,d=2,k,l;
 for(;b/d;++d{      // first half of `p`
  for(k=b;k%d<1;
  k/=d)
   p[d]++;
  for(k=2;p[d]
  &&k<d;
  p[d]*=d%k++>0)
   ;
 }
 for(k=0;n/++k;)    // all factors of $n!$
  for(d=2;k/d
  &&b/d;++d)        // all divisors $d | k$
   for(l=k;p[d]     // which are prime factors of $b$
   &&l%d<1;l/=d)
    ++p[b-~d];
   for(n=d=0;b/++d; /* calculate the minimum of $n!$'s factors
                       weighted according to $b$'s factor's
                       multiplicity */
   k&&n<1|k/p[d]<n
   ?n=k/p[d]:0)
    k=p[b-~d];
 d=n;}              // return
```
[Try it online!](https://tio.run/##jVTJktowEL3zFcpkAC/KGBuzjdHMOedwSNVkqrxIxiob2WWZEGbJr5OWzeoMqehA8Vr9XvfrFkRfllG028WawKH@2kFcVEZBVkGW5ZFmO0aoI8tA37iIGPLDB@L4KMkzKnEHXT@@Ij6QqRGaU0IcwzW00LR19bX@Ykj@wvJYg2K6f3dNaZEwVOSQw0rkFz4qWVEyyUQlUbXJkSyCUjIUlGWwlSiPr8lkTCyrBJo3bR/lItuCR8p@MYrCLSpKvmISowpqxbyU1TUVWeUlF8s6MQwk68uGi@IgUlcvQcVzcdXLV2g6CyplJQmyGNhNPyxjq9qR0mcSZrtBq0Bs/@HHT32ga5uElbASe07SORG@ftGORBteJdcUVuus4kXGI15xJu@QYXUQpsTBKc68DorzUvNCi3qmSV8bhmU106mbh97UPkBdZaYk9NIundvARKlFqK7KFk/02TS9Y47jqQjAXi@dUxVX2CC0m5rmw6DmQPS9s88feMIyzdTT99XhPR6tQflb8el2rw19e6lFa@l90/rB6J5I@U8uFfOWojeUKmZNzUhat3XI3SQ8SuBBsdYsVcGwZvV6WW01O/hEplk8hV9@02fvoCoIhfZDaJ966rcTBVm0ht2z@u2suOCr9epgAja5r3JtWRvGl0kFrzWIoryk9RvMVT9Hal/@x6K39ZZhQ72emNtvqaWMz4UKPQrSwPtmDyglJ0@UCO/9UhUmVbJqXYrdZ8piLhhaqH8PHOkwNlHF2k03QoJ04QcGHz/EDW7@XQiJHvt3/fv@9z5W2OtANrx2LjQdvdaVF9oAO3jfxkKzz4EDwD6A4TlwAQwPYIbH2D0KDLA9GJwypw2enZjT06U9wraDR0c4VnB8rDjD7ghPT8qq09nkHA@xe3HvtvAIO@45HrfuJ9gen@MpHjrneNbig7tWYIgvGxq3ElynVWI2OfM/2E/rvKg6yqg6w3YcDH8Yd5v4uB0fX8lXxuG47TgMQB27HVeD@EgfYtiZTCZ/Xdi1GkiBtffdHw "C (gcc) – Try It Online")
[Answer]
# [Perl 5](https://www.perl.org/) -MList::Util, 131 bytes
131 bytes without newlines, indentation and comments.
```
sub f{
  %d=();                                     #init counting hash to empty
  sub e{$M%$_ or$d{$_}++,$M/=$_,redo for@_}  #sub that counts given factors of $M
  e 2..($M=pop);                             #count factors of M
  (%c,%d)=%d;                                #store and reset counts
  for$M(2..pop){e keys%c}                    #count active factors of N! (N=pop)
  ~~min map$d{$_}/$c{$_},keys%d              #how many of last counts in first
}
```
[Try it online!](https://tio.run/##fZRNb5tAEIbv/hVbskhgNubTYEw29aW3okqWeqorlBpsoZgFAZViIfLTQ/fDCmBQ5wDL8868sztaUSTlZd1lV7CrcfZS/NIPsaaff6NzmRRf9AcdVcUlrfUD0dHTkyQFC0DDQOxpgcdnYHBg3gOrByYH9j1wemALD@ZqGkafshkQf1C06VPMNSMmt1kL4vbEFa19Rpw1I5tbq8EJfG/EbMaccZ4zw7id5YyYO5Pn8c26I8YPYFsj5k/9TGOG8f2Ntmy70zTHmrb1vcHcjOG0P3fCYjAZFvZEExOa15xPzZ1o7n/qblOi4Uw0MS0W5kS7TW2mH0Vc8zzvTmILfheoo7VYnPJS2dVqw5OyqwIJghmCyVuh4h2M@I1/AJA887oXEgOSvNXBLR3Ac17jk6hSBS3KlNRCwMznq5S/Mg6krbRcLr/t9z/20jBVYtpK0TSYqiv6QTAk1BzDDADmwqwAoE7c7kBocdtVf/@AUyPHWFEDtk4aGMowAnkJ4wZGraYhGOoYRqhM4hzQY@6iNgHWaqXAEBd5oQaKfERyrGI5DqgMQ4WKTGgS8JpcK/nYvr9nKQH0xyA8dXhkL8TVuO26j7yo05xU3WP4Pa3q7fZnnV4wrfkH "Perl 5 – Try It Online")
```
print f(100, 13);        # prints 7
print f(1000000, 999);   # prints 27776
```
[Answer]
# MATLAB, 107 bytes
```
function F(n,m)
for i=1:max(n,m),f{i}=factor(i);end
c=f{m};fix(min(sum([f{1:n}]'==c)./sum(c==c')))
end
```
First get all factors from 1 to the maximum of n or m. This guarantees that all factors of 1-n are captured as well as the factors of m. Then, divide the sum of the appearance of each factor by the duplicity of that factor to determine the minimum amount of pairs of the factors of m appear in n!, which is the maximum power that m can be raised to to divide n!.
For example: F(80,100)
1. f -> all factors from 1-100 in a 1x100 cell array, where f{i}=factor(i)
2. c -> [2 2 5 5]
3. sum([f{1:n}]'==c) -> [78 78 19 19], there are 78 2s in all of f and 19 5s in all of f.
4. sum(c==c') -> [2 2 2 2], there are two of each factor
5. (3)/(4) -> [39 39 9.5 9.5]. element-wise division shows that at a minimum, 9 whole sets of factors of m are contained in n!'s factors, therefore n! is divisible by at most m^9
6. fix(min(3.3)) -> 9, which is the correct answer
[Answer]
# [Python 3](https://docs.python.org/3/) + [SymPy](https://www.sympy.org/en/index.html), 118 bytes
```
lambda n,m:min(g(n,f)//p for f,p in factorint(m).items())
g=lambda n,p:n and n//p+g(n//p,p)
from sympy.ntheory import*
```
[Try it online!](https://tio.run/##hZLLcoMgFIb3PgVLaZ1EBFEz45t0Y5uQOBOQMWx8esslSYlzQs9CGb7/3NGLuUyKrqL/Wq@D/D4OSBXyIEeVn3NVCLzfaySmGYlCo1EhMfyYaR6VySXejeYkbznG2bl/@uqDQoM6ImUdP20I@ys0zsQ8SXRbpF52ylxO07ygUeppNh@r9uFEjryVhftWGPU9KnH2CkkKVhEkW0hTkEWQbmHnIfeQbSBx1ZKyBMO2MezgnC3oSWoHSSio3kIeQb6B1FfLag/bV2hLifrsGpjS0OgbX5akIW3FYMqTvk2YBIdpmBOtYNql8pIySUO/8DAoT7myKlVy10CrDfD5YqJ@7J2zeEPOKKy4bymhYH8KDiv4vzEeO7HGYMV9L84IrHjs5l0d9j4omqaBBO4QXrPNUeH1Fw "Python 3 – Try It Online")
---
This is my reference implementation which generate all testcases:
```
from sympy.ntheory import factorint
def f(n, m):
    factor_count = lambda n, p: n // p + factor_count(n // p, p) if n else 0
    return min(factor_count(n, factor) // power for factor, power in factorint(m).items())
```
]