The stupid question is the question not asked PerlMonks

### 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(2..int(sqrt(\$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);

Create A New User
Node Status?
node history
Node Type: note [id://156601]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (9)
As of 2017-07-24 12:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (353 votes). Check out past polls.