factorial trailing zeroes Algorithm
The factorial trailing zeroes algorithm is a mathematical technique used to determine the number of trailing zeroes in the factorial of a given non-negative integer n, denoted as n!. A trailing zero is formed by multiplying a multiple of 5 with a multiple of 2. In simple terms, it calculates how many times a number can be divided by 10 before reaching a non-integer value. This algorithm is particularly useful in solving combinatorics problems or when working with large factorials, which tend to have a significant number of trailing zeroes.
The algorithm works by counting the number of multiples of 5 in the factors of n! since there are generally more factors of 2 than factors of 5, and the number of trailing zeroes depends on the lesser count. To achieve this, the algorithm divides n by 5 and floors the result, then divides the result by 5 again, and continues this process until the result is less than 5. The total sum of the results obtained in each step gives the number of trailing zeroes in the factorial of n. This method effectively calculates the number of pairs of 2 and 5 in the prime factorization of n!, which then helps in determining the number of trailing zeroes present in the factorial.
/*
programme for computing number of zeroes at the end of factorial of a given number n
*/
#include<stdio.h>
#include<math.h> //including math.h header file to use pow function
int main()
{
int i,n,test=0,count=0;
//taking input number n
scanf("%d",&n);
//looping from 1 till loop break
for(i=1;;i++)
{
test=n/pow(5,i);//division of n by ith power of 5(storing in integer form)
if(test!=0) //condition for zeroes at end corresponding individual ith case
{
count=count+test;
}
else
break; //break the loop for if test=0
}
printf("%d\n",count);
return 0;
}
