Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re: ulam's spiral too slow

by kyle (Abbot)
on Apr 16, 2007 at 02:10 UTC ( #610246=note: print w/replies, xml ) Need Help??


in reply to ulam's spiral too slow

A few days back I wrote a prime generator just because I hadn't done it in a while. I thought it came out pretty nice. It caches the primes that it finds and uses them for finding the new ones (that is, it uses the algorithm discussed by other monks: checking each candidate against primes less than the candidate's square root). Here it is:

use strict; use warnings; my @primes = ( 2, 3 ); my $candidate = $primes[-1] + 2; my $max_prime = shift || 100_000; CANDIDATE: while ( $candidate < $max_prime ) { my $sqrt_candidate = sqrt $candidate; PRIME: foreach my $prime ( @primes ) { last PRIME if $prime > $sqrt_candidate; next CANDIDATE if 0 == $candidate % $prime; } push @primes, $candidate; } continue { $candidate += 2; } print join q{,}, @primes; print "\n";

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://610246]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (2)
As of 2021-07-29 02:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?