QM,
I have spent far too many cycles on this. Though it may have been your intention, your original question was not:

Given a number N, find the nearest factor of N less than or equal to the square root of N.

For that question, tall_man's solution is quite concise, efficient, and elegant. Even though I used Math::Pari instead of Math::Big::Factors to get the prime factorization, I interpreted the question to be more about what came after to be important.

My first, solution was straight forward and only had a %seen cache optimization, though I knew other optimizations were possible. Next, I came up with a Inline::C implementation of the first solution (minus the cache). It has turned out to be the fastest by far even without the cache.

Since I was really interested in coming up with a Perl solution that had optimizations, I came up with a second solution. Actually, I came up with about 5 variations on tye's 3 simple rules for generating a powerset in progressive order. The problem in finding the fastest implementation was a strange bug that BrowserUk helped me work around. With that - here is my last attempt (ver_3.pl) 

#!/usr/bin/perl
use strict;
use warnings;
use Math::Pari qw/factorint PARImat/;

print nearest_sqrt( $ARGV[0] );

sub prime_factors {
    my $N = shift;
    my %p_fact = PARImat( factorint( $N ) ) =~ /(\d+)/g;
    return map { ($_) x $p_fact{$_} } sort { $a <=> $b } keys %p_fact;
+ 
}

sub nearest_sqrt {
    my $N = shift;
    my @factor = prime_factors( $N );
    return 1 if @factor == 1;
    my (@subset, %seen, $winner, $offset, $f, $diff);
    my $sqrt = sqrt( $N );
    my $end = $#factor;
    my ($pos, $mode) = (-1, 1);

    while ( 1 ) {
        if ( $mode == 1 ) {
            push @subset, ++$pos;
            ++$mode if $subset[ -1 ] == $end;
        }
        elsif ( $mode == 2 ) {
            splice(@subset, $#subset - 1, 1); 
            ++$mode;
        }
        else {
            return $winner if $subset[ 0 ] == $end; 
            $pos = $subset[ -2 ] + 1;
            splice(@subset, $#subset - 1, 2, $pos); 
            $mode = 1;
        }

        if ( $seen{ "@factor[ @subset ]" }++ ) {
            if ( $mode == 1 ) {
                push @subset, $pos + 1 .. $end;
                ++$mode;
            }
            next;
        }
        $f = 1;
        $f *= $_ for @factor[ @subset ];
        next if $f > $sqrt;

        $diff = ($N / $f) - $f;
        if ( ! defined $offset || $diff < $offset ) {
            ($winner, $offset) = ($f, $diff);
        }
    }
}

[download]
In case you are interested in knowing how well it works, here are some timings for 50_000 random numbers between 1 and 31_415_926_535: 
$ time ./original.pl
real    1m50.885s
user    1m39.513s
sys     0m0.380s

$ time ./inline_c.pl
real    0m35.999s
user    0m31.254s
sys     0m0.590s

$ time ./ver_2.pl
real    1m51.122s
user    1m49.407s
sys     0m0.440s

$ time ./ver_3.pl
real    1m18.209s
user    1m16.810s
sys     0m0.330s

$ time ./tall_man.pl
real    1m23.238s
user    1m15.989s
sys     0m0.500s

[download]
I did try various other solutions in this thread that either ran out of memory (recursive) or just took too long. One note: Roy Johnson's best attempt completes in less than 45 seconds, but unfortunately it has bugs.

Cheers - L~R

In reply to Re: OT: Finding Factor Closest To Square Root by Limbic~Region
in thread OT: Finding Factor Closest To Square Root by QM

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.