In mathematics,the factorial of any positive number N is the product of the positive integers less than or equal to N.It is denoted by ‘N!’.
Example-
5!= 5*4*3*2*1 =120
Also,0!=1.
In C/C++,no data type can store the value of factorial of a number greater than 20.To find the factorial of greater numbers easily,JAVA/Python can be used.
JAVA Code-
This code uses BigIntegers.
[cpp]
import java.io.*;
import java.math.BigInteger;
public class Main
{
public static void main(String[] args) throws IOException
{
String n;
BufferedReader d= new BufferedReader(new InputStreamReader(System.in));
n=d.readLine();
int y=Integer.parseInt(n);
BigInteger x=new BigInteger(n); //converting string to biginteger
for(int j=y-1;j>=1;j–)
{
String str= Integer.toString(j);
x=x.multiply(new BigInteger(str));
}
System.out.println(x);
}
}
[/cpp]
Length of the factorial-
The number of digits in N! is approximately:-
[(log(2*pie*n)/2)+n*(log(n)-1))/log(10)]+1;
Stirling’s approximation-
N! is approximately equal to {sqrt(2*pie*n)}*{(n/e)^n}.
To find the power of a prime factor of N! –
Let the prime factor be X.Then,the power of X will be :-
[N/X]+[N/(X^2)]+[N/(X^3)]+….. where [.] denotes the greatest integer function.
For example-
Power of 2 in 5! will be-
[5/2]+[5/4]+[5/8]+[5/16]+…..
=> 2+1+0+0+….
which is equal to 3.
Also,5!=2^3 * 3^1 * 5^1
To find the number of zeroes at the end of N!-
Find the power of 2 and 5 in N!(Since,10=5*2).
Let it be ‘v’ and ‘s’ respectively.
if(v<=s),then number of zeroes at the end is 'v',else,'s'.
Code-
[cpp]
//initialization
s=0;
v=0;
p=N; //copying value of N to another variable
//Finding power of 5
while(N>0)
{
q=N/5;
s=s+q;
N=q;
}
//Finding power of 2
while(p>0)
{
w=p/2;
v=v+w;
p=w;
}
if(v>=s) printf("%d\n",s);
else printf("%d\n",v);
}
[/cpp]
Last Non-zero digit of the factorial-
Lets say D(N) denotes the last non zero digit of factorial, then the algo says:-
If tens digit of N is odd,D(N)=4*D[N/5]*D(Unit digit of N)
If tens digit of N is even,D(N)=6*D[N/5]*D(Unit digit of N)
where [N/5] is greatest Integer Function.
Example-
D(26)=6*D[26/5]*D(6)=6*D(5)*D(6)=6*2*2=4
[D(5) means last non zero digit of 5!=120 which is 2, same for D(6)]
