Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

How not to do prime factorization

by thisisdada (Acolyte)
on Jun 30, 2015 at 14:05 UTC ( #1132616=obfuscated: print w/replies, xml ) Need Help??

$"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:

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.

for$b(-25..25){for$a(-50..29){$x=$a/21;$y=$b/15;print$b?chr:chr^chr ord(substr'<6C}'.1x29 .'[FDEq2?@E96Cqa6C=q924',$a)-49;$_=30;($y,$x) =(2*$x*$y+$b/15,$x*$x-$y*$y+$a/21)while$x*$x+$y*$y<9&$_++<95}$_=10}

Replies are listed 'Best First'.
Re: How not to do prime factorization
by atcroft (Abbot) on Jun 30, 2015 at 16:46 UTC

    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:

    Enjoy.

Re: How not to do prime factorization
by QM (Parson) on Jun 30, 2015 at 15:49 UTC
    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;

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: obfuscated [id://1132616]
Approved by Athanasius
Front-paged by Arunbear
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2017-12-11 03:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What programming language do you hate the most?




















    Results (286 votes). Check out past polls.

    Notices?