Click Here to see the problem detail.

Solution

Step1: Assign all prime number up to 101 to an array.

Prime number up to 101 = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 57, 59, 61, 67, 71, 73, 79, 83, 87, 97,101

How you will get these prime number ? Just run a programm as follows:

[codebox 1]

Step2: Find out how many times a prime number repeat in a factorial of given input.

Explanation:  suppose your  input is 5. Now 5!=5*4*3*2*1. If you want to find out how many times 2 is repeated in 5! then you are thinking to do this as follows:

Pseudocode:

input =5;

factorial-of-input=5*4*3*2*1

counter=0;

while(factorial-of-input)

{

if(factorial-of-input%2==0)

counter=counter+1;

factorial-of-input=factorial-of-input/2;

}

how many times 2 is repeated in 5! is save in counter. But if you think as simple as above you are in wrong track. suppose I say do this for 10000 as input. You are saying I can’t handle it because there is no big variable to store 10000!

You are a programmer to handle all exception.  Okay let me explain a trick to do that.  Suppose your input is n and you want to find out how many times m is repeated in n! as a factor.  to do this use the following rules: 

how many times m is repeated in n! = n/m +n/m2 +n/m3+n/m4+…..

it will continue until the fractional value (n/m4) is greater than or equal 1.

N.B: The  part of the fraction  will be added. suppose, n/m =1.6 then 1 will be added.

Source Code

 


Next Previous