Wednesday, July 30, 2008

The Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm to calculate prime numbers. It involves starting at 2 and removing all numbers that can be divided by it evenly. You then go to the next number remaining and do the same, repeating until you have reached the end of your finite list of numbers.

Here is my perl implementation. Be gentle. I'm just learning the language. Post constructive comments if you have any ideas about what I could have done better.

Note: Blogger isn't allowing me to format the code properly. It all works*, but it looks ugly. It is much nicer looking in Komodo Edit and vim.

#!/usr/bin/perl -w
#The Sieve of Eratosthenes
use strict;

if($#ARGV != 0){
print "Usage: sieve.pl n \nn must be an integer greater than 1\n";
exit;
}
my $max = $ARGV[$1];
if($max < 2){
print "Argument must be larger than 1\n";
exit;
}
my @list = (1..$max);
my @sublist = ();
my @primes = ();
my $current = 0;
my $i = 0;
my $list_length = 0;

$list_length = @list;
my $nonzero = 1;
while ($nonzero){
for($i = $nonzero; $i < $list_length; $i++){
if($list[$i] != 0){
$nonzero = $i;
last;
}
elsif($i == $list_length - 1 && $list[$i] == 0){
$nonzero = 0;
last;
}
}
$current = $list[$nonzero];
for($i = $nonzero; $i < $list_length; $i++){
if($list[$i] % $current == 0){
$list[$i] = 0;
}
}
push(@primes, $current) if $nonzero;
}
print "@primes\n";

*There is something wrong with line 9. It works, but it says, "Use of uninitialized value in array element at sieve.pl line 9." I don't yet know how to fix this, but it returns the proper results.

No comments: