neo_ has asked for the wisdom of the Perl Monks concerning the following question:

Hi all! I'm a Perl newb and I'm writing a Sieve of Eratosthenes. I know users have GOLF'd it on this site but GOLFing is way down the road for me. Anyway, here's what I have: 
#!/usr/bin/perl

print "Show primes up to: ";
chomp($max = <>);

@n = (2..$max);
@f = (2..sqrt(@n));

foreach $i (@f) {
        @e = grep {$_ % $i != 0}  @n;
        @n = ();
        @n = @e;
}

print "@n\n";

./sieve.pl
Show primes up to: 21
5 7 11 13 17 19

[download]
Pretty good! Wait...it is cutting out the 2 and 3. And if I go higher: 
./sieve.pl
Show primes up to: 31
7 11 13 17 19 23 29 31

[download]
That's no good. Can someone help show me what i'm missing? Not looking for an answer, just looking for a shove in the right direction. Any help is appreciated.

Replies are listed 'Best First'.
Re: What am I missing?
by moritz (Cardinal) on Aug 11, 2009 at 06:41 UTC
    Your script does not print out a 2 because because it removes all numbers divisible by 2. What it should do is preserve the first one.

    The least intrusive change to your program to get it working is this: 

    foreach $i (@f) {
        @n = grep {$_ % $i != 0 || $_ == $i }  @n;
}

    [download]
[reply]
[d/l]
Re: What am I missing?
by Anonymous Monk on Aug 11, 2009 at 02:07 UTC
[reply]
      Alright, in words... The object is to get all prime numbers up to and including our input. First we take the lowest number, which in this case is 2. We need to eliminate all multiples of that number. In other words, create an array where the element values divided by 2 yields a remainder. At this point we have an array of nothing but stuff that is NOT divisible by 2. This is our new list, so we save it. Now we go up to 3 and repeat, saving our new array as we go. Ahhh, I see what's going on. The first element in each new array is greater than the element we are going to divide by. So it leaves 0 and a remainder. I need to use a floor or int function. Stay tuned...
[reply]
Re: What am I missing?
by JavaFan (Canon) on Aug 11, 2009 at 12:48 UTC
    That's not a "Sieve of Eratosthenes". You're testing with all the numbers between 2 and the square root of the max. Eratosthenes was smarter than that. He knew only to test with the primes. The primes you're generating.

    Anyway, your problem is that you remove the prime itself from @n. Don't do that. 

    my $max = shift || 100;
my @nums = (2 .. $max);
my @primes;

while (@nums) {
    my $prime = shift @nums;
    push @primes, $prime;
    if ($prime ** 2 > $max) {
        push @primes, @nums;
        last;
    }
    @nums = grep {$_ % $prime != 0} @nums;
}

say "@primes";

    [download]
[reply]
[d/l]
      Much thanks to all for their helpful hints. I have learned from this thread.
[reply]
Re: What am I missing?
by psini (Deacon) on Aug 11, 2009 at 04:13 UTC

    This part:

    foreach $i (@f) {
        @e = grep {$_ % $i != 0}  @n;
        @n = ();
        @n = @e;
}

    [download]

    could be shortened as:

    foreach $i (@f) {
  @n = grep {$_ % $i != 0} @n;
}

    [download]

    without making it less readable.

    The problem in your implementation is that you take off @n every multiple of $i, including $i! Try:

    foreach $i (@f) {
  @n = grep {$_ % $i != 0 || $_ == $i} @n;
}

    [download]

    Updated: jwkrahn is right, this @n = grep {$_ % $i != 0} @n foreach $i (@f); would not work.

    Rule One: "Do not act incautiously when confronting a little bald wrinkly smiling man."

[reply]
[d/l]
[select]
      This part:

      foreach $i (@f) { @e = grep {$_ % $i != 0} @n; @n = (); @n = @e; }

      could be shortened as:

      @n = grep {$_ % $i != 0} @n foreach $i (@f);

      No it cannot because the statement modifier foreach does not support the syntax foreach $i (@f), it only works as foreach @f with $_ as the current element.

[reply]
[d/l]
[select]

Back to Seekers of Perl Wisdom