Not sure if this is correct either, but I checked a few cases and it appears to work. Is there a good method of verification?

It starts to get slow with big numbers, but it's much quicker than factors_wheel() finding the prime factors, for all the cases I tried.

There appears to be a bug in the overloading in Math::Big, hence the de-Bignumming map.

Update: Version 3. Anyone care to break this one for me?

#! perl -slw
use strict;
use overload;
use Math::Big::Factors qw[ factors_wheel ];
use List::Util qw[ reduce min ];
use Algorithm::Loops qw[ NestedLoops ];

my $NUM = $ARGV[ 0 ] || 996;

my $root = sqrt $NUM;
my @pfs = reverse map{ "$_" } factors_wheel( $NUM );

print "$NUM primefactors ( @pfs )";

my $n = $pfs[ 0 ];

while( @pfs > 1 ) {
#    print "@pfs";

    my $near = reduce{ 
        ( $a * $b ) <= $root ? $a*$b : $a
    }  @pfs;
#    print "$near : ", $NUM%$near;

    $n = $near 
        if ( $NUM % $near ) == 0 
        and abs( $root - $near ) < abs( $root - $n );

    my $discard = shift @pfs;
    next if $pfs[ 0 ] == $discard;
    unshift @pfs, $pfs[0] while $root > reduce{ $a * $b } @pfs;
}

print "$NUM ($root} : $n";

__END__
P:\test>432558 1995
1995 primefactors ( 19 7 5 3 )
1995 (44.6654228682546} : 35

P:\test>432558 1994
1994 primefactors ( 997 2 )
1994 (44.6542271235322} : 997

P:\test>432558 1993
1993 primefactors ( 1993 )
1993 (44.6430285710994} : 1e+099

P:\test>432558 1993
1993 primefactors ( 1993 )
1993 (44.6430285710994} : 1993

P:\test>432558 1994
1994 primefactors ( 997 2 )
1994 (44.6542271235322} : 997

P:\test>432558 1995
1995 primefactors ( 19 7 5 3 )
1995 (44.6654228682546} : 35

P:\test>432558 9999999
9999999 primefactors ( 4649 239 3 3 )
9999999 (3162.27750205449} : 2151

P:\test>432558 99999999
99999999 primefactors ( 137 101 73 11 3 3 )
99999999 (9999.99995} : 7373

P:\test>432558 999999999
999999999 primefactors ( 333667 37 3 3 3 3 )
999999999 (31622.7765858724} : 2997

P:\test>432558 1000
1000 primefactors ( 5 5 5 2 2 2 )
1000 (31.6227766016838} : 25

P:\test>432558 2000
2000 primefactors ( 5 5 5 2 2 2 2 )
2000 (44.7213595499958} : 40

P:\test>432558 20000
20000 primefactors ( 5 5 5 5 2 2 2 2 2 )
20000 (141.42135623731} : 125

P:\test>432558 200000
200000 primefactors ( 5 5 5 5 5 2 2 2 2 2 2 )
200000 (447.213595499958} : 400
[download]

#! perl -slw
use strict;
use overload;
use Math::Big::Factors qw[ factors_wheel ];
use List::Util qw[ reduce min ];
use Algorithm::Loops qw[ NestedLoops ];

my $NUM = $ARGV[ 0 ] || 996;

my $root = sqrt $NUM;
my @pfs = reverse map{ "$_" } factors_wheel( $NUM );

print "$NUM primefactors ( @pfs )";

my $n = 0;

while( $root <= reduce{ $a * $b } @pfs ) {
    my $near = reduce{ 
        ( $a * $b ) <= $root ? $a*$b : 0+$a
    }  @pfs;
    $n = $near 
        if abs( $root - $near ) < abs( $root - $n );
    $n = $near * $pfs[ -1 ] 
        if abs( $root - $n ) > ( $near * $pfs[ -1 ] - $root );
    my $discard = shift @pfs;
    next if $pfs[ 0 ] == $discard;
    unshift @pfs, $pfs[0] while $root > reduce{ $a * $b } @pfs;
}

print "$NUM ($root} : $n";

__END__
P:\test>432558
996 primefactors ( 83 3 2 2 )
996 (31.559467676119} : 36

P:\test>432558 1000
1000 primefactors ( 5 5 5 2 2 2 )
1000 (31.6227766016838} : 32

P:\test>432558  100000000000000
100000000000000 primefactors ( 5 5 5 5 5 5 5 5 5 5 5 5 5 5 2 2 2 2 2 2
+ 2 2 2 2 2 2 2 2 )
100000000000000 (10000000} : 10000000

P:\test>432558  10000000000000
10000000000000 primefactors ( 5 5 5 5 5 5 5 5 5 5 5 5 5 2 2 2 2 2 2 2 
+2 2 2 2 2 2 )
10000000000000 (3162277.66016838} : 3125000

P:\test>432558  1995
1995 primefactors ( 19 7 5 3 )
1995 (44.6654228682546} : 35
[download]