---

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² +n/m³+n/m⁴+…..

it will continue until the fractional value (n/m⁴) 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.

#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