Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
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: (9)
As of 2015-07-02 01:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (25 votes), past polls