How will I find out factorial from prime number? (c programming)

Question

Problem :

Now you have to solve an interesting problem. Any integer n (where 1 < n < 100, means values ​​of n from 2 can be up to 99) to find the number of times a prime number exists by expressing the factorial of have to do Like, we know, 5! = 120 = 2 * 2 * 2 * 3 * 5. Here 2 is 3 times, 3 is 1 time and 5 is 1 time. So if the input is 5 the output will be: 5! = (2, 3), (3, 1), (5, 1). Do you understand one thing that at the beginning of n ?Is it going to be a hassle to figure out the value of the factorial and then break the original product? Because the value of n is maximum 99 and integers cannot hold the factorial value of any number greater than 12. "Actually this program doesn't need to figure out the value of n!. Just do a little math. And put the prime numbers from 2 to 99 into an array."

I can't understand how will I find out factorial from prime number? Please give me some clue .

Here, the author said, "Actually this program doesn't need to figure out the value of n!. Just do a little math. And put the prime numbers from 2 to 99 into an array."
My question is how will I find out the factorial from this array (prime number) Suppose, I copy the prime numbers into an array then ?

Answer 1

The prime factors of n! are the prime factors of n, plus the prime factors of n-1, plus the prime factors of n-2, ..., plus the prime factors of 2.

5!
= (2, 0), (3, 0), (5, 1)    // 5
+ (2, 2), (3, 0), (5, 0)    // 4
+ (2, 0), (3, 1), (5, 0)    // 3
+ (2, 1), (3, 0), (5, 0)    // 2
= (2, 3), (3, 1), (5, 1)    // 5!

That means the largest number we need to factorize is n, and the largest prime we need to deal with is at most n.

Another interesting property is that each prime in [2,n] is guaranteed to appear once.

---

1. Ahead of time, create primes, an array of all the primes from 2 to 100.

   primes = [
       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
   ]
   

2. Set num_primes to the number of primes in that array.

   num_primes = 25
   

3. Create counts, an array of size num_primes initialized to zeroes.

4. For term = 2 to n by 1,

   1. Set r to term.
   2. For prime_idx = 0 to min(num_primes-1,term) by 1,
      1. While r is greater than zero and the remainder of r and primes[prime_idx] is zero,
         1. Increment counts[prime_idx].
         2. Subtract primes[prime_idx] from r.

That's it. We want the prime factors of the each term of the factorial. The outer loop visits each term of the factorial, and the inner loop finds the prime factors of the current term.

For n = 5, you end up with

// 5! = 2^3 * 3^1 * 5^1
primes = [ 2, 3, 5, ... ]
counts = [ 3, 1, 1, ... ]

---

#!/usr/bin/perl

use v5.14;
use warnings;

# Supports 0 <= $n < 101
my @primes = (
    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,
);

my $n = shift // 5;

my @counts = ( 0 ) x @primes;
for my $term ( 2 .. $n ) {
   my $r = $term;

   PRIMES:
   for my $prime_idx ( 0 .. $#primes ) {
      while ( $r % $primes[ $prime_idx ] == 0 ) {
         ++$counts[ $prime_idx ];
         $r -= $primes[ $prime_idx ];
         last PRIMES if !$r;
      }
   }
}

say
   join ", ",
      map { "($primes[ $_ ], $counts[ $_ ])" }
         grep { $counts[ $_ ] }
            0 .. $#primes;

$ ./a.pl 5
(2, 3), (3, 1), (5, 1)

$ ./a.pl 100
(2, 1275), (3, 289), (5, 73), (7, 32), (11, 1),
   (13, 1), (17, 1), (19, 1), (23, 1), (29, 1),
   (31, 1), (37, 1), (41, 1), (43, 1), (47, 1),
   (53, 1), (59, 1), (61, 1), (67, 1), (71, 1),
   (73, 1), (79, 1), (83, 1), (89, 1), (97, 1)

Answer 2

You don't need to calculate the factorial of that number. You can simply do it in this way.

#include <stdio.h>

int main()
{
    int a[] = {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};
    int sum = 0;

    for(int n = 1; n<=100; n++){
        printf("%d! = ", n);
    for(int i = 0; i < 25; i++){
        for(int j = 1; j <= n; j++){
            if((j*pow(a[i],1))<=n) sum++;
            if((j*pow(a[i],2))<=n) sum++;
            if((j*pow(a[i],3))<=n) sum++;
            if((j*pow(a[i],4))<=n) sum++;
            if((j*pow(a[i],5))<=n) sum++;
            if((j*pow(a[i],6))<=n) sum++;
      }
      if(sum!=0)
      printf("(%d,%d),",a[i], sum);
        sum = 0;
      }
       printf("\n");
    }
}

Answer 3

So You want to find prime factorization of a factorial instead of factorial value itself. The naive way of computing this is simply test subresult divisibility agains primes and move the value from factorial to array of exponents to keep the subresult small. For example like this in C++:

//---------------------------------------------------------------------------
const 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,103,107,109,113,127,131,137,139,149,151,157,163,167,173};
const int primes=sizeof(prime)/sizeof(prime[0]);
//---------------------------------------------------------------------------
void fact0(int *pexp,const int &x)
    {
    int i,j,c;
    for (j=0;j<primes;j++) pexp[j]=0;// clear exponents
    for (c=1,i=2;i<=x;i++)          // process factorial
        {
        c*=i;                       // update factorial subresult c
        for (j=0;(j<primes)&&(c>=prime[j]);j++)
        while (c%prime[j]==0)       // if c is divisible by prime
            {
            c/=prime[j];            // divide by it to keep c small
            pexp[j]++;              // and adjust exponent for that prime
            }
        }
    }
//---------------------------------------------------------------------------

where pexp[primes] holds exponents of prime factotrization (corresponding to prime[]) of your factorial. You can enhance this by using binary search however for such small n! I doubt it would be practical.

There are however more advanced (and much faster) ways of obtaining this for example see:

• Fast exact bigint factorial

after adapting it to your task the code looks like this:

//---------------------------------------------------------------------------
const 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,103,107,109,113,127,131,137,139,149,151,157,163,167,173};
const int primes=sizeof(prime)/sizeof(prime[0]);
//---------------------------------------------------------------------------
void fact1(int *pexp,const int &x)
    {
    int N4,N2,p,i,j,e,c[primes];
    // hardcoded return for small x!
    if (x<=4)
        {
        for (i=0;i<primes;i++) pexp[i]=0;
        if (x==4){ pexp[0]+=3; pexp[1]++; return; } // 24
        if (x==3){ pexp[0]++; pexp[1]++; return; } // 6
        if (x==2){ pexp[0]++; return; } // 2
        if (x==1){ return; }            // 1
        if (x==0){ return; }            // 1
        }
    // bigger x! compute to local temp c[]
    for (i=0;i<primes;i++) c[i]=0;
    N4=(x>>2)<<2;
    N2=N4>>1;
    fact1(c,N2);                        // c=(2N)!
    for (i=0;i<primes;i++) c[i]+=c[i];  // c=((2N)!)^2
    for (i=0;i<primes;i++)              // c*= T2
        {
        p=prime[i];
        if (p>N4) break;
        for (e=0,j=N4;j;e+=j&1,j/=p);
        c[i]+=e;                        // c*=p^e
        }
    for (e=1,i=N4+1;i<=x;i++)           // handle remaining 0-3 multiplications
        {
        e*=i;
        for (j=0;(j<primes)&&(e>=prime[j]);j++)
         while (e%prime[j]==0) // if e is divisible by prime
            {
            e/=prime[j]; // divide by it to keep c small
            c[j]++;      // and adjust exponent for that prime
            }
        }
    // copy finished answer to destination array and return
    for (i=0;i<primes;i++) pexp[i]=c[i];
    return;
    }
//---------------------------------------------------------------------------

I just changed the bigints c and all its operation to array of exponents.

This is how I used/test it in VCL using TMemo for output (you can use cout or whatever instead):

int x=35;
AnsiString s;
int i,pexp[primes];
fact0(pexp,x); for (s="",i=0;i<primes;i++) if (pexp[i]){ if (s!="") s+="."; s+=AnsiString().sprintf("(%i^%i)",prime[i],pexp[i]); } mm_log->Lines->Add(s);
fact1(pexp,x); for (s="",i=0;i<primes;i++) if (pexp[i]){ if (s!="") s+="."; s+=AnsiString().sprintf("(%i^%i)",prime[i],pexp[i]); } mm_log->Lines->Add(s);

Here result for 35! using both methods:

(2^32).(3^15).(5^8).(7^5).(11^3).(13^2).(17^2).(19^1).(23^1).(29^1).(31^1)
(2^32).(3^15).(5^8).(7^5).(11^3).(13^2).(17^2).(19^1).(23^1).(29^1).(31^1)

Beware if you want bigger factorials the you have to enlarge the primes list first ...