Product of Prime factors of a number

Question

Given a number X , what would be the most efficient way to calculate the product of the prime factors of that number? Is there a way to do this without actual factorisation ? Note-The product of prime factors is needed (all to the power unity).

Answer 1

This answer addresses the second half of your question - i.e. is it possible to compute the product of the prime factors without factorising the number. This answer shows that it is possible to do, and shows a method that is more efficient than a naive method of factorisation. However, as noted in the comments, this proposed method is still not as efficient as factorising the number using a more advanced method.

Let k be the cube root of the number.

Check the number for all primes of size k or smaller and divide out any we find.

We now know that the resulting number is a product of primes larger than k, so it must either be 1, a single prime, or a product of 2 primes. (It cannot have more than 2 primes because k is the cube root of the number.)

We can detect whether it is a product of 2 primes by simply testing whether the number is a perfect square.

The results of this allow us to calculate the result in O(n^(1/3) / log(n)) assuming we have precomputed a list of primes.

EXAMPLE 1

Suppose we have the number 9409.

The cube root is 21.1 so we first check for divisibility by primes under 21.

None of them find a result so we compute the sqrt and find 9409== 97**2.

This means that the answer is 97.

EXAMPLE 2

Suppose we have the number 9797.

The cube root is 21.4 so we check for divisibility by primes under 21.

None of them find a result so we compute the sqrt and find 9797 is not a perfect square.

Therefore we conclude the answer is 9797. (Note that we have not determined the factorisation to work out this answer. In fact the factorisation is 97*101.)

Answer 2

Maple and Mathematica both calculate the squarefree kernel of a number by factoring and then multiplying back together just one copy of each prime (see https://oeis.org/A007947) so I doubt a better way is known.