$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";