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

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 ?

CodePudding user response：

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.

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
]

Set num_primes to the number of primes in that array.
```
num_primes = 25
```
Create counts, an array of size num_primes initialized to zeroes.
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)

CodePudding user response：

So You want to find prime factorization of a factorial instead of factorial value itself. The naive way of computing this is (beware I did not test the code I just wrote it directly):

int i,j,f,n=55;
int p[]={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,0}; // primes up to 100
int e[sizeof(p)/sizeof(p[0])]; // prime exponents
for (j=0;p[j];j  ) e[j]=0; // clear expnents
for (f=1,i=2;i<=n;i  ) // process factorial
   {
   for (j=0;p[j];j  ) // if i is prime
    if (i==p[j])      // add it to exponent
      {
      e[j]  ;
      j=-1; break;
      }
   if (j<0) continue;
   f*=i;              // if not adjust factorial remainder f
   for (j=0;(p[j])&&(f>=p[j]);j  ) // if f is divisible by prime
    while (f%p[j]==0) // adjust exponent and f
      {
      f/=p[j];
      e[j]  ;
      }
   }

Now e[] holds the exponents of prime factotrization 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 ways of obtaining this for example see:

Fast exact bigint factorial

so you can obtain the exponents by using the same recursion and the therm:

for (ee=0,j=N4;j;ee =j&1,j/=p);

You just instead of c*=p^ee do e[i] =ee this will be much faster due lover complexity and no need for expensive division testing. The only thing you need to add is changing c=((2N)!)^2; simply by multiplying all the exponents in e[] by 2 and hardcode the first n<=4 cases.