#!/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 $sqrt = sqrt( $N );
    my @factor = prime_factors( $N );
    return 1 if @factor == 1;
    my $end = $#factor;
    my @subset;
    my ($pos, $mode) = (-1, 1);

    my %seen;
    my $get_factor = sub {
        if ( $seen{ "@factor[ @subset ]" }++ ) {
            if ( $mode == 1 ) {
                push @subset, $pos + 1 .. $end;
                ++$mode;
            }
            return undef;
        }
        my $f = 1;
        $f *= $_ for @factor[ @subset ];
        return $f < $sqrt ? $f : undef;
    };


    my %dispatch = (
        1 => sub {
            push @subset, ++$pos;
            ++$mode if $subset[ -1 ] == $end;
            return 1;
        },
        2 => sub {
            splice(@subset, $#subset - 1, 1); 
            return $mode++;
        },
        3 => sub {
            return () if $subset[ 0 ] == $end; 
            $pos = $subset[ -2 ] + 1;
            splice(@subset, $#subset - 1, 2, $pos); 
            return $mode = 1;
        },
    );

    my ($winner, $offset);

    while ( $dispatch{ $mode }->() ) {
        my $factor = $get_factor->() or next;

        my $diff = ($N / $factor) - $factor;
        if ( ! defined $offset || $diff < $offset ) {
            ($winner, $offset) = ($factor, $diff);
        }
    }
    return $winner;
}
[download]