Re: 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);
[download]

Note: the grep is fairly costly. Find a better algorithm if you're looking for all primes up to, say, 100,000.

Comment on Re: Prime Number Finder Download Code

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);` [download]	[reply] [d/l]

Replies are listed 'Best First'.

Re: Re: Prime Number Finder
by Anonymous Monk on Nov 03, 2003 at 05:34 UTC

! 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);
[download]

[reply]
[d/l]