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).

Stonybroke

This isn't clear. Naively the answer is just return X;... – Calculated

Not that my ignorance says much, but I know of no way to compute the squarefree kernel of an arbitrary X without knowing the prime factors of X. – Reg

AFAIK, the answer to this is NO, there is no way to derive the product of prime factors of a single number that is more efficient (Big O-wise) than factoring that number. However, you might find more knowledgeable/expert answers over at cs.stackechange.com – Bright

Thinking about it a little, calculating product(p) where p is the prime factors of n, seems to be effectively equivalent computationally to calculating product(p-1), which is Euler's Totient function. I've done programs to do that, and they all required factoring n one way or another. Indeed, the strength of the RSA encryption schemes relies on Totient(n) being as hard as factoring n. – Bright

Your question is unclear. Do you want the product of all the prime factors or just of the unique prime factors? That is, given the number 28, which has prime factors (2,2,7), would you want the answer to be 14? – Albers

Yes, product of the unique prime factors. – Stonybroke

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.)

Jorgan

This is not more efficient than factoring the number. – Bright

@Bright what is the complexity of factorising? I was assuming a naive method of trying all primes up to the sqrt of the number. – Jorgan

@PeterdeRvaz Factorization is a very complex and sophisticated field that is better answered by Google and Wikipedia than me. However, the first question you should be asking yourself is, "is what I am proposing faster than or even just different from factoring?" The answer so far is No, everything you are suggesting are also common tricks in naive factorization. – Bright

nice trick, lets us to not finish up the factorization in full... but real sophisticated factorization algos are much faster anyway. so this trick is worth it only when compared with the simple trial division, not the sophisticated stuff like elliptic curve factorization. IOW if you can do ECF, it'll be much faster to do full factorization with it than half-factorization by trial division with this trick (talking big numbers, of course). – Epencephalon

2*11*13*13=3718. Cube root is 15.49... All prime factors fall below that, so we'll get 1 after dividing them out. Or did I misunderstand your approach? – Permittivity

@BertteVelde That is right, at the end you need to multiply by all the prime factors you have found. – Jorgan

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.

Azine

Answer 3

Another approach is to start with the number itself. It is obviously a product of all its prime factors. You want to remove all the factors with power more than one. Hence, you don't mind if the number has a factor 2, but you do mind if it has a factor 4 (2^2). We can solve the problem by removing the extra factors.

Simple pseudocode:

method removeHigherPrimePowers(number)
  temp <- number
  primes <- [2, 3, 5, 7 ...]
  for each p in primes
    factor <- p * p  // factor = 4, 9, 25, ...
    while (temp MOD factor = 0)
      temp <- temp / p  // Remove extra factor of p
    endwhile
  endfor
  return temp
endmethod

The number is being factorised, but the factorising is somewhat hidden. All those MOD statements do the same work. All that is being saved is a certain amount of accounting, keeping track of the factors found so far and multiplying them all together at the end.

As Peter says, you can test all primes up to the cube root, and then check if the number remaining is square.

Malign

The while loop exits when temp MOD factor != 0. The value of temp changes each time round the loop in temp <- temp / p. At some point the loop will exit. – Malign

It will terminate in any computer that has less than infinite storage. The size of the primes list can be set according to the range of values of the input test number X, which is not specified in the question. I left it open for that reason. – Malign