Just another Perl shrine PerlMonks

### How not to do prime factorization

 on Jun 30, 2015 at 14:05 UTC 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

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 cooling their heels in the Monastery: (7)
As of 2018-02-20 20:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When it is dark outside I am happiest to see ...

Results (274 votes). Check out past polls.

Notices?