Need help to understand Perl code implementing Sieve of Eratosthenes

Question

I found the following code written in Perl about the Sieve of Eratosthenes (an algorithm to find primes in a given range of numbers) and it's working fine, but I don't understand it. Can somebody comment it out for me, so I'll get a better understanding of how the primes are found?

$max= 120; 
@primes= ();
@tested= (1);
$j= 1;
while ($j < $max) {
   next if $tested[$j++];
   push @primes, $j;
   for ($k= $j; $k <= $max; $k+=$j) {
      $tested[$k-1]= 1;
   }
}
print "@primes\n";

Answer 1

$max= 120; 
@primes= ();

$tested might be better named something like $nonprime. Although we put 1 into the array to start with, it doesn't actually do anything useful... it could equally be left empty.

Also, @tested isn't a list of non-primes, but a list of boolean values whose indices are non-primes. If, for some reason, you wanted to mark 2 as non-prime, you'd have to do something like this instead: @tested = (1,1);

@tested= (1);
$j= 1;

Sweep through all the integers from 1 to 120.

while ($j < $max) {

If we've already checked this number for primality and it failed, restart the loop to check the next number.

   next if $tested[$j++];

We now know that j is a prime, because we haven't marked it as being non-prime, so we can add it to the end of our list. The final list will be in ascending order because of this.

   push @primes, $j;

Sweep through every remaining number between this one and the end of the array. We increment by our new prime number each time, so we're basically striding over all the multiples of $j

   for ($k= $j; $k <= $max; $k+=$j) {

Mark each multiple as tested. We know it cannot be prime, as it has $j as a factor.

      $tested[$k-1]= 1;
   }
}

The rest of the script is left as an exercise for the reader.

print "@primes\n";

Answer 2

I would rewrite (clean up) that script like the following to make it more clear.

Take this as lesson that if one gives variables meaningful names, code can become self-documenting:

use strict;
use warnings;

my $max = 120;
my @primes;
my @notprime;

for my $num (2..$max) {
    next if $notprime[$num];
    push @primes, $num;
    for (my $multiple = 2 * $num; $multiple <= $max; $multiple += $num) {
        $notprime[$multiple] = 1;
    }
}
print "@primes\n";

The wikipedia article on Sieve of Eratosthenes is going to explain the algorithm fully, and provide pretty little visuals on the process. However, the summary is just this:

• Iterate over all the integers from 2 to max.
• If an integer hasn't been marked as notprime, then it's prime!
• Then just cycle through all multiples of the recognized prime so that we can mark them as not prime.