Largest Square Factor

[BigMoosie]

I need to write a function to find the largest square factor of a number so it can be taken out of a radical. I hope there is a known solution to this.

 

The most efficient aproach I can think of is:

 

set total to 1
for (each prime less than square root of n) {
 while (n is divisble by prime^2) {
   divide n by prime^2
   multiply total by prime
 }
}

"total" should then be a square factor of n. The problem with this is that it is very slow. Is there a faster method?

[matt grime]

Total is not a sqaure factor of n, unless I misunderstand what 'square factor' means, ie a factor that is a square. total is not a square. total will be a square root of a square factor.

 

in anycase, how are you using this? because it seems to me that given N you put N in, and get N' out but then you need to put N' in again, and so on until it outputs what you input.

 

This seems unwieldy. Firstly, your program should run something we'll label 'IsSquare( )', then it should at the very least do something like:

 

 

if p divides N work out largest power of p that divides N, if even exponent do something if odd do sometihng

 

 

however, this essentially factors N, so you might as well just ask for the factorization and read off the answer.

 

 

what size input are you considering and what length of time do you need to do this in?