in reply to OT: Finding Factor Closest To Square Root
Doesn't use Math::Big::Factor, isn't particularly dynamic, doesn't have exponential complexity, and could be much faster in C. With all those caveats, here you go...
#!/usr/bin/perl w
use strict;
print sqrt_factor(shift), "\n";
sub sqrt_factor
{
my $n = shift;
my $root = int(sqrt($n));
for (my $i=$root; $i>1; $i)
{
if( ($n % $i) == 0 )
{
my $factor2 = int($n / $i);
return (($root  $i)<($factor2  $root)) ? $i : $factor2
}
}
return 1;
}
 All code is 100% tested and functional unless otherwise noted.
Re^2: OT: Finding Factor Closest To Square Root by QM (Parson) on Feb 20, 2005 at 07:20 UTC 
Yes, but this still takes a long time for large prime N, as it has to count down from sqrt(N) to 1.
It would go twice as fast if we checked N%2==0. It would go six times as fast if we checked for N%3==0 also. Perhaps using GCD(N,sqrt(N)#) (where N# is the primorial of N) would improve the situation? The problem then becomes one of generating all primes upto sqrt(N), where we could cheat and just have a big list precomputed.
...Better yet, would a quick test of N for primality solve the problem of prime N?
QM

Quantum Mechanics: The dreams stuff is made of
 [reply] [d/l] [select] 
