#!/usr/bin/perl

use CGI qw(:standard -nph);

$|=1;

print "HTTP/1.0 200 OK\n";
print "Pragma: no-cache\n";
print "Content-type: text/html\n\n";

print "<title>Prime Number Generator</title>\n";

$limit =1000000;
$limitSqrt = int(sqrt($limit));

print "Prime Numbers up to $limit<br>\n";

# $prime{$num} = 3 $num is prime
# $prime{$num} = undef $num not known at this point
# $prime{$num} = 1 $num is not prime

for($num=2; $num <= $limitSqrt; ++$num)
     {
     $sum = $num;
     if (!$prime{$num}) #this number has not been marked 'not prime' so it must be prime
         {
         #$prime{$num} = 3;
         print "$num\n"
         }
     while ($sum < $limit) #mark all non primes up to limit
             {
             $sum = $sum + $num;
             $prime{$sum} = 1; #not prime
             }
     }

for($num=$limitSqrt; $num < $limit; ++$num)
     {
     #if ((!$prime{$num}) or ($prime{$num} == 3))
     if (!$prime{$num})
         {
         #$prime{$num} = 3;
         print "$num\n"
         }
     else {
           #$prime{$num} = 1
           }
     }

=pod
for($num=2; $num < $limit; ++$num)
     {
     if ($prime{$num} == 3) {print "$num\n"}
     }
=cut

1;