How not to do prime factorization

[thisisdada]

$"x=$%="@ARGV";$~=$;='(  +)';while($%>>$:++){if($"=~/$~$/^$"=~/$;$/){$
|=$?=$:>2||die"prime\n";eval"print length(\$$?)".($:>++$?&&"/length(\$
$?).'*'")while$:>$?;die$/}$;=$~;$~=~s~.*~^($&\\1+)~;$~=~s;\d+;1+$&;eg}

The best thing I can say about this code is that it works. It will take a number via argv give you the prime factorization of that number... eventually. It's not very efficient. At all. I had a lot of fun writing it, but it's really bad at what it does. To give you an idea of how erratic it is, here are some benchmarks:

<Reveal this spoiler or all in this thread>

While it can distinguish primes at a reasonable rate, it takes a really long time to factor composite numbers. Particularly composite numbers made up of several small primes. Powers of 2 are the worst-case scenario.

[atcroft]

Here was my simplistic factoring one-liner, and its results on the first digits from pi (1-11).

Code:

perl -Mstrict -Mwarnings -le 'my $n = shift or die qq{Requires 1 numbe
+r argument.}; my $o = $n; my @f = (); my $i = 2; while ( $n % $i == 0
+ ) { push @f, $i; $n /= $i; } $i++; while ( $n >= $i ) { while ( $n %
+ $i == 0 ) { push @f, $i; $n /= $i; } if ( $n > $i ) { $i += 2; } } p
+rint $o, q{ = }, join q{*}, @f;'

Output:

Read more... (2 kB)

Enjoy.

[QM]

Geez! A really naive regex solution is very quick, but limited to <= 65535:

#!/usr/bin/env perl
use strict;
use warnings;

my $candidate = shift;
my $candidate_string= ('x' x $candidate);

while (1) {
    if (my ($factor,$rest) = $candidate_string=~ m/^(..+?)(\1+)$/) {
        print length($factor), "*";
        $candidate /= length($factor);
        $candidate_string= ('x' x $candidate);
    } else {
        print $candidate;
        last;
    }
}

print "\n";

exit;