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

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
The brute-force would be very slow:

#include <stdio.h>
int fact(int n);
int main(void) {
  int current;
  printf("Enter a positive integer [to terminate enter non-positive] > ");
  scanf("%d", &t);
  while (current > 0) {
    printf("The factorial of %d is %d\n", current, fact(current));
    printf("Enter a positive integer [to terminate enter non-positive] > ");
    scanf("%d", &t);
  }
}

/* n is a positive integer. The function returns its factorial */
int fact(int n) {
  int lcv;    /* loop control variable */
  int p;      /* set to the product of the first lcv positive integers */

  for(p=1, lcv=2; lcv <= n; p=p*lcv, lcv++);
  return p;
}