Re: Prime Number Finder

[eisenstein]

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.

[Anonymous Monk]

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);