Your skill will accomplishwhat the force of many cannot PerlMonks

### Re^5: Number functions.. primes (ugly code runs faster)

by danaj (Friar)
 on May 01, 2015 at 06:31 UTC Need Help??

All of the code for primes() I've seen on this thread are 2-10x slower than any of the four shown on RosettaCode for this task.

If you want the fastest speed, use the ntheory module -- is_prime for primality testing, primes or forprimes or one of the related functions for generating primes. This will be a few orders of magnitude faster.

• Comment on Re^5: Number functions.. primes (ugly code runs faster)

Replies are listed 'Best First'.
Re^6: Number functions.. primes (ugly code runs faster)
by Anonymous Monk on May 02, 2015 at 17:20 UTC

Sounds like a challenge. I took the dj_string routine on rosettacode and simplified it some.

```sub sieve_s2 {
my (\$n, \$i, \$s, \$d, @primes) = (shift, 7);

my \$sieve = '110010101110101110101110111110' .
'101111101110101110101110111110' x (\$n/30);

for (\$sieve) {
until ((\$s = \$i*\$i) > \$n) {
\$d = 2*\$i;
do { substr(\$_, \$s, 1, '1') } until (\$s += \$d) > \$n;
1 while substr(\$_, \$i += 2, 1);
}
\$_ = substr(\$_, 1, \$n);
push @primes, pos while m/0/gogo;
return @primes;
}
}
Pure perl isn't up to warp-speed, understandably.

Very nice. About 1.5x faster, better looking code, though 2x memory use.

Addendum: Can you put it on RosettaCode or let me know it's ok to put there? Everything there gets covered by the GNU FDL so I don't want to put there without some sort of permission. More code improvements are also welcome :)

Regarding memory use: the result array footprint probably outweighs the sieve for limits up to 1014.

Re: code. m//gogo is the sole bit of artistic liberty (or wishful thinking) and can be shortened to just //g. And sure, you're welcome to it, to work on it or repost it. An anonymonk couldn't say no, anyhow.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1125331]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chanting in the Monastery: (4)
As of 2024-02-24 03:20 GMT
Voting Booth?
My favourite way to spend a leap day ...

Results (22 votes). Check out past polls.