Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
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.


Comment on Re: OT: Finding Factor Closest To Square Root
Download Code
Re^2: OT: Finding Factor Closest To Square Root
by QM (Vicar) 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

Log In?
Username:
Password:

What's my password?
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?
Others surveying the Monastery: (3)
As of 2014-09-02 04:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (19 votes), past polls