Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re: Prime Number Finder

by eisenstein (Acolyte)
on Apr 04, 2002 at 07:45 UTC ( #156601=note: print w/replies, xml ) Need Help??

in reply to Prime Number Finder

I offer the following as a balance of speed, elegance, and brevity, or at the very least, a demonstration of TMTOWTDI. The algorithm is: take the first number off the top of the list, call it a prime, filter the rest of the list for multiples, repeat.
use strict; sub primes { my @n = (2..shift); my @p; while (@n && (push @p, shift @n)) { @n = grep { $_ % $p[-1] } @n; } return @p } # find all primes through 100 print join ',',primes(100);
Note: the grep is fairly costly. Find a better algorithm if you're looking for all primes up to, say, 100,000.

Replies are listed 'Best First'.
Re: Re: Prime Number Finder
by Anonymous Monk on Nov 03, 2003 at 05:34 UTC
    eisenstein's code is genius, to say the least. I found a different way of the sieve method, and am wondering which is more efficient. Thanks!
    ! usr/bin/perl -w use strict; sub prime{ my (@primes,%n); my $n=shift; foreach my $r(2..$n){ $n{$r}=1; } foreach my $x($n))){ if($n{$x}){ my $a=2*$x; while ($a <= $n){ $n{$a}=undef; $a=$a+$x; } } } foreach my $x(2..$n){ if($n{$x}){ push( @primes, $x); } } return @primes; } #find to 100 print join ',',prime(100);

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (6)
As of 2021-05-13 16:54 GMT
Find Nodes?
    Voting Booth?
    Perl 7 will be out ...

    Results (137 votes). Check out past polls.