Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

Re: Prime Number Finder

by eisenstein (Acolyte)
on Apr 04, 2002 at 07:45 UTC ( [id://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);

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

    [download]
[reply]
[d/l]

In Section Cool Uses for Perl

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: note [id://156601]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? • Last hour • Other CB clients
Other Users?
Others pondering the Monastery: (3)
As of 2024-04-25 17:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found