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;
[download]