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
Don't
#! 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
>
Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.