prime factorization of factorial in C

Question

I'm trying to write a program that will print the factorial of a given number in the form: 10!=2^8 * 3^4 * 5^2 * 7 To make it quick lets say the given number is 10 and we have the prime numbers beforehand. I don't want to calculate the factorial first. Because if the given number is larger, it will eventually go beyond the the range for int type. So the algorithm i follow is: First compute two’s power. There are five numbers between one and ten that two divides into. These numbers are given 2*1, 2*2, …, 2*5. Further, two also divides two numbers in the set {1,2,3,4,5}. These numbers are 2*1 and 2*2. Continuing in this pattern, there is one number between one and two that two divides into. Then a=5+2+1=8.

Now look at finding three’s power. There are three numbers from one to ten that three divides into, and then one number between one and three that three divides into. Thus b=3+1=4. In a similar fashion c=2. Then the set R={8,4,2,1}. The final answer is:

10!=2^8*3^4*5^2*7

So what i wrote is:

#include <stdio.h>
main()
 {
     int i, n, count;
     int ara[]={2, 3, 5, 7};
     for(i=0; i<4; i++)
     {
         count=0;
         for(n=10; n>0; n--)
         {
            while(n%ara[i]==0)
            {
                count++;
                n=n/ara[i];
            }
         }
         printf("(%d^%d)" , ara[i], count);
     }
     return 0;
   }

and the output is (2^3) (3^2) (5^1) (7^1). I can't understand what's wrong with my code. Can anyone help me, please?

A debugger is the ideal tool to help you out in this situation. — kaylum, Jul 25 '16 at 06:42
Your while loop variable should be different from the for loop variable. — Abhishek Bansal, Jul 25 '16 at 06:44
wrong approach, in particular this line ` n=n/ara[i];` what are u trying to do here? — Yerken, Jul 25 '16 at 07:08
What my formula was: The prime factors between one and ten are 2, 3, 5, and 7 so S={2,3,5,7}. Then 10! can be written in the form: 10!=(2^a)*(3^b)*(5^c)*7 First compute two’s power. There are five numbers between one and ten that two divides into. These numbers are given 2, 4, 6, 8, 10. Further, two also divides two numbers in the set {1,2,3,4,5}. Continuing in this pattern, there is one number between one and two that two divides into. Then a=5+2+1=8. same process for the rest of the primes. That's why i use that line. To divide n untill the quotient is no more an integer. — Ruhel Ahmed Raktim, Jul 25 '16 at 07:26
factorial prime factorizations creates specific computable pattern in form of regular series. If you derive the series equation per each prime you can output the result directly without the search. I did something similar in past for different reasons see [Fast exact bigint factorial](http://stackoverflow.com/q/18317648/2521214). Also swinging primes may be a worth looking at as they are a bit closer to what you are trying to achieve. — Spektre, Jul 25 '16 at 10:01

score 1 · Accepted Answer · answered Jul 25 '16 at 08:01

Much simpler approach:

#include <stdio.h>

int main(int argc, char const *argv[])
{
    const int n = 10;
    const int primes[] = {2,3,5,7};
    for(int i = 0; i < 4; i++){
        int cur = primes[i];
        int total = 0;
        while(cur <= n){
            total += (n/cur);
            cur = cur*primes[i];
        }
        printf("(%d^%d)\n", primes[i], total);
    }
    return 0;
}

score 0 · Answer 2 · answered Jul 25 '16 at 07:37

Your code divides n when it is divisible for some prime number, making the n jumps.

e.g. when n = 10 and i = 0, you get into while loop, n is divisible by 2 (arr[0]), resulting in n = 5. So you skipped n = [9..5)

What you should do is you should use temp when dividing, as follows:

#include <stdio.h>
main()
 {
 int i, n, count;
 int ara[]={2, 3, 5, 7};
 for(i=0; i<4; i++)
 {
     count=0;
     for(n=10; n>0; n--)
     {
        int temp = n;
        while(temp%ara[i]==0)
        {
            count++;
            temp=temp/ara[i];
        }
     }
     printf("(%d^%d)" , ara[i], count);
 }
 return 0;

}

score -3 · Answer 3 · edited Jul 25 '16 at 08:24

-3

For finding factorial of a no pl. try this code:

#include <stdio.h>

int main()
{
  int c, n, fact = 1;

  printf("Enter a number to calculate it's factorial\n");
  scanf("%d", &n);

  for (c = 1; c <= n; c++)
    fact = fact * c;

  printf("Factorial of %d = %d\n", n, fact);

  return 0;
}

edited Jul 25 '16 at 08:24

Garf365

3,619
5
29
41

answered Jul 25 '16 at 07:15

Keyur Buch

41
4

1

This does not answer the question. – Abhishek Bansal Jul 25 '16 at 07:27
That's the problem. If the given number is larger, the factorial will be out of range for int type. So what i'm trying to do is to find the prime factorization without computing the factorial of the number. – Ruhel Ahmed Raktim Jul 25 '16 at 07:29

prime factorization of factorial in C

3 Answers3