laziness, impatience, and hubris | |
PerlMonks |
Re^6: OT: Finding Factor Closest To Square Rootby hv (Prior) |
on Feb 21, 2005 at 10:15 UTC ( [id://432995]=note: print w/replies, xml ) | Need Help?? |
The original question started "given N and N's prime factorization", so it seems inappropriate to take into account the time taken to factorize. In this case though, note that 988041964007 = 7 x 11087 x 12731023 - you are losing accuracy by throwing out the BigInts. In general if the factorization of N is taking longer than it takes to do sqrt(N) trial divisions then the factorization algorithm is pretty bad, since "trial division up to the square root" is the classical example of a slow algorithm. Many of the high precision maths libraries out there do factorization - for example the pari library (Math::Pari) has a factorint() function:
Note that this algorithm does not guarantee primality: for large factors you need to verify with an isprime() check. Hugo
In Section
Seekers of Perl Wisdom
|
|