# COME ON CODE ON

A blog about programming and more programming.

## Factorial

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,  4! = 1 x 2 x 3 x 4 = 24

In programming, factorial comes to use at many places. Sometimes you simply have to calculate factorials but in C/C++ you are limited by the range of integers. Even long long can store only up-to 20! .

```int main()
{
long long i,j=1;
for (i=1;i<21;i++)
{
j*=i;
printf("%lld! = %lld\n",i,j);
}
}&#91;/sourcecode&#93;

So you have to find factorials using strings and multiply the way you used to do in std I or II. If you haven't done so do now, you will learn a lot. Or if you know some language like Python or Haskell, which allow larger numbers you need not worry. For example,  a code to accept t number of test cases and then print the factorial of next t numbers(less than 100) in python would be :

&#91;sourcecode language='python'&#93;

f=&#91;1&#93;*101
for i in range(2,101):
f&#91;i&#93;=f&#91;i-1&#93;*i

n=input()
for i in range(0,n):
x=input()
print f&#91;x&#93;&#91;/sourcecode&#93;

Sometimes the question can be to find n! as a power of primes. To know the power of prime in a factorial you can use the formula:
<em>                  ε</em><sub>p</sub> = ⌊n/p⌋ + ⌊n/<em>p</em><sup>2</sup>⌋ + ⌊n/<em>p</em><sup>3</sup>⌋...

where <em>ε</em><sub>p</sub> is the power of prime p in factorial n.

<strong>Number of trailing zeroes in n Factorial</strong>

Finding number of trailing zeroes is very easy. Because you can get a zero only through a multiple of 5. So the number of trailing zeroes is equal to the multiples of five which is :
<em>                         ε</em><sub>5</sub> = ⌊n/5⌋ + ⌊n/<em>5</em><sup>2</sup>⌋ + ⌊n/<em>5</em><sup>3</sup>⌋...

A simple c-sharp program to get t test cases and then output the number of trailing zeroes in the factorial of next t numbers would be :

using System;

class Program
{
public static void Main()
{
int T, N, sum, x;
while (T>0)
{
x = 5;
sum = 0;
while (N / x > 0)
{
sum += N / x;
x *= 5;
}
Console.WriteLine(sum);
T--;
}
}
}```

I will be writing soon on how to find the last non-zero digit and if possible also last k non zero digits.

ciao
fR0D

Written by fR0DDY

June 20, 2009 at 12:39 PM

Posted in Programming

Tagged with , , , , , , , , ,

### 6 Responses

1. An interesting way to calculate a factorial is to compute them at compilation time rather than computing them at runtime using C++ template metaprogramming.

Code taken from wikipedia:

```template <int N>
struct Factorial
{
enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0>
{
enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
int x = Factorial<4>::value; // == 24
int y = Factorial<0>::value; // == 1
}```

dominiko

June 20, 2009 at 3:28 PM

2. Hey, thanks dominiko, for pointing me to that!

fR0D

June 20, 2009 at 3:33 PM

3. […] COME ON CODE ON A blog about programming and more programming. « Factorial […]

4. Hey,
I assume u are using SyntaxHighlighter plugin in wordpress to display these code snippets. Can u tell me how u r doing it? Do we need to have a wordpress.org account to be able to use that plugin?
Also, i see that u are using LateX too? What plugin is used for that?

Thanks!

aj

October 26, 2009 at 3:44 AM

5. Thanks a lot!

ajaygopalakrishnan

October 26, 2009 at 9:03 AM