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

my $num = $ARGV[0];
print nearest_sqrt($num, prime_factors( $num ) ) || 'prime'; 

sub prime_factors {
    my $num = shift;
    my %p_fact = PARImat( factorint( $num ) ) =~ /(\d+)/g;
    return [ map { ($_) x $p_fact{$_} } keys %p_fact ]; 
}
__END__
__C__

int nearest_sqrt (double num, SV* input) {
    int len = av_len((AV *)SvRV(input));
    int tot = len + 1;
    int i = 0;
    double list[ tot ];
    int position[ tot ];
    int stop[ tot ];
    double offset = -1;
    int end_pos;
    int done = 0;
    int winner = 0;
    int by = 0;
    int next = 1;


    while ( i <= len ) {
        list[ i ] = SvNV(* av_fetch((AV *)SvRV(input), i, 0));
        ++i;
    }

    while ( done == 0 ) {
        int j;
        int cur;
        double factor;
        double diff;
        if ( next == 1 ) {
            int c = 0;
            int p = 0;
            int s = 0;
            ++by;
            if ( by > tot ) break;
            if ( by >= 2 ) {
                for (p = 0; p <= by - 2; ++p) {
                    position[ p ] = p;
                }
            }
            position[ p ] = by - 2;
            end_pos = p;
            for ( s = tot - by; s <= len; ++s ) {
                stop[ c ] = s;
                ++c;
            }
            next = 0;
        }
        cur = end_pos;
        while ( 1 ) {
            if ( ++position[ cur ] > stop[ cur ] ) {
                int k;
                int new_pos;
                position[ --cur ]++;
                if ( position[ cur ] > stop[ cur ] ) continue;
                new_pos = position[ cur ];
                for (k = cur; k <= end_pos; ++k) {
                    position[ k ] = new_pos++;
                }
            }
            break;
        }
        if ( position[0] == stop[0] ) {
            if ( position[0] == tot ) {
                done = 1;
            }
            else {
                next = 1;
            }
        }

       factor = 1;
       for (j = 0; j <= end_pos; ++j) {
           factor *= list[ position[ j ] ];
       }
       diff = (num / factor) - factor;
       if ( diff >= 0 && (offset == -1 || diff < offset) ) {
           winner = factor;
           offset = diff;
       }
    }
    return( winner );
}
[download]