#!/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);
        }
    }
}

##</code><code>##

$ 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