# Find the factorial of a given number n (big) --> n!

Note: this is to find the factorial of n!

Different with the problem of find the factorial of arbitrary number, please check <http://www.wikihow.com/Factor-a-Number>

Very good and clear explanation:
http://en.wikipedia.org/wiki/Integer_factorization
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[Problem]
The nth factorial, n!, can be computed straightforwardly by multiplying together the range of integers 1, 2, ... n from the bottom up. However, if n is large, this becomes inefficient. The k:th subproduct has roughly k log k digits, so multiplying by k+1 (assumed to fit in a single machine word) takes k log k time. This leads to a total time of O(n2 log n) for calculating n!.
Many algorithms exist for splitting a product of many factors into smaller pieces to balance the size of each subproduct. However, there is a trick to factorials: we can find the prime factorization of n! quickly, much more quickly than we can compute n! itself. And we can do this without stepping through the list 1, 2, ..., n and factorizing each of these numbers. The crucial observation is that n! must necessarily contain each prime number up to n, and that the power of the prime p in n! is given by


Suppose we find the prime number is p1, p2, p3....
corresponding power is a, b, c,....
we have n! = p1^a * p2^b * p3^c.

[Solution]
-1- Step 1 ---> find the prime number
Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) is a simple, ancient algorithm for finding all prime numbers up to a specified integer.[1] It works efficiently for the smaller primes (below 10 million).[2]
A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.
To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)
4. Find the first number remaining on the list after p (this number is the next prime); replace p with this number.
5. Repeat steps 3 and 4 until p2 is greater than n.
6. All the remaining numbers in the list are prime.

<<sieve of Eratosthenes>>=http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
unsigned char* prime_table(int n) {
  int p, j;
  unsigned char* sieve = (unsigned char*)calloc(n+1, sizeof(unsigned char));
  sieve[0] = sieve[1] = 1;
  for (p=2; p*p <= n; p++)
      if (sieve[p] == 0)
          for (j=p*p; j <= n; j+=p)   \\ this one is even better that j start fro p*p not 2p
              sieve[j] = 1;
  return sieve;
}

-2- Step 2 ---> find the power of each prime number
After generate this table, the next step is to calculate the power of each prime number that the given n consiste, which is to calculate a, b, and c....
n! = p1^a * p2^b * p3^c.  --> use
that the power of the prime p in n! is given by

{please pay attention to the difference of n and n!}
<<compute multiplicity of a prime in factorial n>>=
/* Return the power of the prime number p in the
 factorization of n! */
int multiplicity(int n, int p) {
  int q = n, m = 0;
  if (p > n) return 0;
  if (p > n/2) return 1;
  while (q >= p) {
      q /= p;
      m += q;
  }
  return m;
}

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

Other links: http://en.literateprograms.org/Factorials_with_prime_factorization_%28C%29