In this post, we’ll see how to count the trailing zeros in a factorial. We’ll start with a short definition of the problem. Then we’ll show an algorithm to calculate them and finally implement it in C.
The widget below is an example implementation. It will return the trailing zeros for the factorial of a number in any base between 2 and 256. In order to avoid too extensive calculations, it’s limited to numbers less than one million. Note that the number is expressed initially in decimals (base 10). Invalid input will return -1.
Zeros: 0
Trailing zeros in a factorial
The factorial of a number (n!) is the multiplication of all the numbers less than or equal to that number:
n! = n * (n -1) * … * 1
What we’ll do in this post is to calculate the trailing zeros of n!. For example, 15! equals 1307674368000, which means it has 3 trailing zeros.
Additionally, the trailing zeros will be calculated for a specific base. The calculations above, for example, were done on base 10 (decimal numbers).
Some common bases are:
-
2(binary numbers). -
8(octal numbers). - And
16(hexadecimal numbers).
Counting trailing zeros algorithm
To simplify this explanation, let’s consider only decimal numbers first.
Retaking the example above, we had that 15! equals 1307674368000. Once the factorial has been calculated, it’s straight-forward getting the number of trailing zeros. However, calculating a factorial is a computation-intensive process that grows very rapidly. For example, 100! is already more than 150 digits long.
Since we don’t really care about the factorial value but only about its trailing zeros, we’ll see how to count the trailing zeros without calculating the factorial.
See that 15! can be expressed as:
15! = someValue * 10^3
Where someValue is some number irrelevant for us. The important part is that the factorial contains three factors of 10. Each trailing zero is a factor of 10 that can be factored from the factorial. Since 15! contains three 10 factors, it has 3 trailing zeros.
This means that the number of trailing zeros equals the number of times we can factor 10 from the factorial.
In more general terms:
The factorial of a number
nin basebhas as many trailing zeros as factors ofbthat can be factored fromn!.
Once again: we can factor 10 (the base), 3 times from 15!. Thus the number of trailing zeros in 15! is 3.
This is the algorithm that we’ll use to count trailing zeros in a factorial.
Implementation: counting trailing zeros in a factorial
The first step will be to get the prime factors of the base (which is passed as an argument). Since we’re limiting the base to a maximum of 256, we’ll need only the prime numbers less than this value. To avoid using an extra function to calculate prime numers, we’ll use a pre-calculated list of primes less than 256 (primes).
#define SIZE 54
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251};
int i, n;
int primeCount[SIZE] = {0};
for (n=base, i=0; n != 1 && i<SIZE; i++) {
while (n % primes[i] == 0) {
n /= primes[i];
primeCount[i]++;
}
}
SIZE is the length of the primes array: 54. The count of prime factors in the base are stored in the primeCount array. The factor count of prime number prime[i] is stored at the corresponding index in the prime count array:primeCount[i].
Next, for each prime factor of the base, we’ll count how many times it can be factored from the factorial of number (passed as an argument). We’ll divide that factor count in the factorial by the factor count in the base calculated in primeCount. The lesser of these divisions for all factors in the base is the number of trailing zeros.
For example, let’s say the base is 45 = 3*3*5. The prime factors are 3 and 5. However, the factor count of prime factor 3 is 2 while the factor count of 5 is only 1. This means that to factor 45 from the factorial, we’ll need twice as many factors of 3 than factors of 5.
int factorCount, minCount=-1;
for (i=0; i<SIZE; i++)
if (primeCount[i] != 0) {
factorCount = getFactorialFactorCount(number, primes[i]) / primeCount[i];
if (minCount == -1)
minCount = factorCount;
if (factorCount < minCount)
minCount = factorCount;
}
The value of minCount is initialized to -1. It’s then replaced by the first factorCount calculated. Every time a lower value is found, the value of minCount is updated. Once the loop finishes, the value of minCount is the actual number of trailing zeros in the factorial.
To make the last calculation, we used a helper function getFactorialFactorCount:
int getFactorialFactorCount(int number, int prime)
{
int n, count, factor;
for (count=0, n=2; n<=number; n++)
for (factor=n; factor % prime == 0; factor /= prime, count++)
;
return count;
}
This function will calculate the number of times we can factor prime from the factorial of number.
And that’s it!
Putting all of the pieces together we have:
#include <stdio.h>
#define SIZE 54
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251};
int zeros(int base, int number);
int getFactorialFactorCount(int number, int prime);
int main()
{
int zeroCount;
zeroCount = zeros(8, 64);
printf("There are %d zeros.\n", zeroCount);
return 0;
}
int zeros(int base, int number)
{
int i, n, minCount=-1, factorCount;
int primeCount[SIZE] = {0};
for (n=base, i=0; n != 1 && i<SIZE; i++) {
while (n % primes[i] == 0) {
n /= primes[i];
primeCount[i]++;
}
}
for (i=0; i<SIZE; i++)
if (primeCount[i] != 0) {
factorCount = getFactorialFactorCount(number, primes[i]) / primeCount[i];
if (minCount == -1)
minCount = factorCount;
if (factorCount < minCount)
minCount = factorCount;
}
return minCount;
}
int getFactorialFactorCount(int number, int prime)
{
int n, count, factor;
for (count=0, n=2; n<=number; n++)
for (factor=n; factor % prime == 0; factor /= prime, count++)
;
return count;
}
We compile the code above to calculate the number of trailing zeros in the factorial of 64 in base 8 as an example. We get:
$ gcc factorialtail.c -o main $ ./main There are 21 zeros
With this, we have concluded this explanation of how to calculate the number of trailing zeros of the factorial of a number in a certain base.