Re: Factoraization of n! as power of primes

[Arturo Magidin]
...
I misread the original and cancelled my posting.

I thought the original poster wanted to obtain BOTH the list of primes
and their exponents. Of course, it is easy, given a prime p and a
positive integer n, to find the exponent of p in the factorization of
n!. But there is no easy way to find all the primes that occur in the
factorization of n! given only n; at least, no known way.

The set of primes dividing n! is the set of primes <= n, and you surely
don't mean to say there's no known way to find the latter. Perhaps "easy"
is an informal notion of efficiency here? For example, the sieve of
Eratosthenes is "easy" by most measures, but does take time mildly
super-linear in n (and fancier sieve methods exist that are mildly
sub-linear in n; since there are about n/log(n) primes <= n, O(n/log n) is a
lower bound).

Otherwise, figuring out if n is a prime would be easy, not to
mention factoring: just factor n! and factor (n-1)! to find a
factorization for n.

Sounds more efficient than "surrogate factoring" anyway ;-)


.

Relevant Pages