## 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); } }[/sourcecode] 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 : [sourcecode language='python'] f=[1]*101 for i in range(2,101): f[i]=f[i-1]*i n=input() for i in range(0,n): x=input() print f[x][/sourcecode] 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; T = int.Parse(Console.ReadLine()); while (T>0) { N = int.Parse(Console.ReadLine()); 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

Advertisements

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:

dominikoJune 20, 2009 at 3:28 PM

Hey, thanks dominiko, for pointing me to that!

fR0DJune 20, 2009 at 3:33 PM

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

Last Non-zero Digit of Factorial « COME ON CODE ONJune 20, 2009 at 6:12 PM

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!

ajOctober 26, 2009 at 3:44 AM

You do not need any plugins to do that. Just have a look at the support section. More precisely http://en.support.wordpress.com/code/ for code syntax highlighter and http://en.support.wordpress.com/latex/ for latex.

fR0DOctober 26, 2009 at 8:30 AM

Thanks a lot!

ajaygopalakrishnanOctober 26, 2009 at 9:03 AM