snippet
tye
I recently realized the power of base-1 numbers. They don't have the arbitrary range limitations of Perl's regular number representations while converting between the two is nearly trivial. Plus finding prime base-1 numbers is particularly compact code in Perl. And when the primality test fails you are also handed some factors! So base-1 numbers are <b>perfect</b> for finding prime factorizations! They aren't very space efficient, unfortunately (hey, no one's perfect).
<p>
So factor1() returns the prime factorizations of base-1 numbers (as base-1 numbers). factor10() just converts a base-10 number into a base-1 number so factor1() can factor it and then converts the returned list of base-1 factors into base 10 again.
<p>
One line of test code is included that factors any base-10 numbers given on the command line.
<p>
Now <b>updated</b> to be faster!
<CODE>
#!/usr/bin/perl -w
use strict;
sub factor1 {
return @_ if $_[0] !~ /^(..+?)\1+$/;
return map { factor1($_) }
( "$1", $_[0] =~ s/$1/1/g, $_[0] )[0,-1];
}
sub factor10 {
return map {length} factor1( 1x$_[0] );
}
print join $/, map { join " ", factor10($_) } @ARGV;
</CODE>