Prime factorization of factorial

Question

Is it possible to find prime factors of factorial without actually calculating the factorial?

My point here is to find prime factors of factorial not of a big number. Your algorithm should skip the step of having to calculate the factorial and derive prime factors from n! where n <= 4000.

Calculating the factorial and finding it's prime divisors is pretty easy, but my program crashes when the input is greater than n=22. Therfore I thought it would be pretty convinent to do the whole process without having to calculate the factorial.

function decomp(n){
  var primeFactors = [];
  var fact = 1;

  for (var i = 2; i <= n; i++) {
     fact = fact * i;
  }

  while (fact % 2 === 0) {
    primeFactors.push(2);
    fact = fact/2;
  }

  var sqrtFact = Math.sqrt(fact);
    for (var i = 2; i <= sqrtFact; i++) {
    while (fact % i === 0) {
      primeFactors.push(i);
      fact = fact/i;
      }
  }

   return primeFactors;
}

I don't expect any code nor links, exemplifactions and a brief outline is enough.

Possible duplicate of [Algorithm to find Largest prime factor of a number](https://stackoverflow.com/questions/23287/algorithm-to-find-largest-prime-factor-of-a-number) — Ken White, May 23 '19 at 17:43
This is more a maths question than a programming question, but yes, it's possible, and even easy. The exponent of each prime `p` in the prime factorization of `n` is `floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...`. (Stop when `n / p^k` is less than `1`.) — Mark Dickinson, May 23 '19 at 18:05
@MarkDickinson: You should turn that into an answer. This is a better algorithm than the one in the only current answer (though you wrote `n` rather than `n!` at one point). — Rory Daulton, May 23 '19 at 20:47
Possible duplicate of [Prime factorization of a factorial](https://stackoverflow.com/questions/21196814/prime-factorization-of-a-factorial) — Will Ness, May 26 '19 at 11:30
see [my answer](https://stackoverflow.com/a/21235844/849891) on the duplicate for a nice (I think) illustration. — Will Ness, May 26 '19 at 12:10

score 1 · Answer 1 · answered May 23 '19 at 19:43

1

Let's consider an example: 10! = 2^8 * 3^4 * 5^2 * 7^1. I computed that by computing the factors of each number from 2 to 10:

 2: 2
 3: 3
 4: 2,2
 5: 5
 6: 2,3
 7: 7
 8: 2,2,2
 9: 3,3
10: 2,5

Then I just counted each factor. There are eight 2's (1 in 2, 2 in 4, 1 in 6, 3 in 8, and 1 in 10), four 3's (1 in 3, 1 in 6, and 2 in 9), two 5's (1 in 5, and 1 in 10), and one 7 (in 7).

In terms of writing a program, just keep an array of counters (it only needs to be as large as the square root of the largest factorial you want to factor) and, for each number from 2 to the factorial, add the count of its factors to the array of counters.

Does that help?

answered May 23 '19 at 19:43

user448810

17,381
4
34
59

So there should be a loop that goes from 2 to n and then it divides actual iteration into it's prime divisors which are stored in an array. If i understood your solution properly my code from above should like this: https://jsfiddle.net/kapiko112/pkv07Lhj/ – Excell May 23 '19 at 20:01
You don't need me to look at your code. Run it and let us know if it works. – user448810 May 23 '19 at 20:35
The array of counters only need to hold one count for each prime number less than the number you are factorialing (?). For 50! you will just need primes up to 47: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. – rossum May 24 '19 at 08:00
Tthats right so by holding only one count in an array the performance of such programme will be decent. But that still doesnt give me the expected output. The programme should completely defactorize the number n! into its components and store each prime number with itsapproproate exponent. Thats exactly what @Mark Dickinson algorithm does. – Excell May 24 '19 at 16:29

Prime factorization of factorial

1 Answers1