 Don't ask to ask, just ask PerlMonks

### Re: OT: Finding Factor Closest To Square Root

by sleepingsquirrel (Hermit)
 on Feb 19, 2005 at 17:04 UTC ( #432755=note: print w/replies, xml ) Need Help??

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.

Replies are listed 'Best First'.
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

Create A New User
Node Status?
node history
Node Type: note [id://432755]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?