**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/m ^{2} +n/m^{3}+n/m^{4}+…..**

it will continue until the fractional value (**n/m ^{4}**) 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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<stdio.h> #include<math.h> int main() { int n,i,j,flag,count; int prime[]= {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101}; while(1) { int factors[60]= {0}; count=0; i=0; flag=0; scanf("%d",&n); if(n==0) break; while(prime[i]<=n) { for(j=1; j<=7; j++) { factors[i]+=n/pow(prime[i],j); } i++; } printf("%3d! =",n); for(j=0; j<i; j++) { count++; if(flag==1) { printf(" "); /*6 spaces */ flag=0; } printf("%3d",factors[j]); if(count%15==0) { printf("\n"); flag=1; } } if(count%15) printf("\n"); } return 0; } |

Next Previous