Tuesday, January 08, 2008

Sieve of Eratosthenes (Perl)

Followup to a previous Java implementation (that blogger botched), here is the Perl scriptage:

print "\n=======================\n";
print "=======================\n";
# Get the range
print "Minimum value of primes: ";
my $min = <STDIN>;
chomp $min;
print "Maximum value of primes: ";
my $max = <STDIN>;
chomp $max;
# Create a max-sized array
my @primes = (1...$max);
# Initially assume all numbers are prime
for($i = 0; $i < $max; $i++) {
$primes[$i] = 1;
# The sieve
for ($i=2; $i*$i <= $max;$i+=1) {
if ($primes[$i]) {
for ($j=$i; $j*$i < $max; $j+=1) {
$primes[$i * $j] = 0;
# Show the results
my @p = ();
for ($i=$min; $i<=$max; $i++) {
if ($primes[$i]) {
push @p, $i;
$size = @p;
print qq(Found $size primes:\n@p\n);


Jester said...

That's a nice, elegant implementation. Thank you, you just saved me some work.

You may want to edit your post to escape the angle brackets around STDIN because they are getting rendered as bad HTML and therefore not displaying.

laptop battery said...

I do not kown this,'$' like php,'print' like c\c#\java and so on,and asp is 'code' jsp and .net just like it,when i looked at this,author,i am sure you are a developer,I want to make friend with you,I kown php,jsp,asp,c,c#,c++,java,and .net

G said...

Wow, thanks!

Charles said...

This is almost perfect. There is one exception you forgot and that is the number 1 is not a prime number. The smallest prime is 2.