#!perl #Sieve of Eratosthenes use Benchmark; $N = 60; if ($ARGV[0]) { $N = $ARGV[0]; print "N> $N\n"; } $true = 1; $false = 0; # 1. create a list of natural numbers 2, 3, 4, ... none of which is marked. for ($i=2;$i<=$N;$i++) { $a[$i] = 1; } # 2. Set k = 2, the first unmarked number on the list. $k = 2; $t1 = new Benchmark; # 3. Repeat while ($k**2 <= $N) { # a. Mark all multiples of k between k^2 and N for ($i=$k**2; $i<=$N; $i++) { if (($i % $k) == 0) { $a[$i] = 0; } } # b. Find the smallest number greater than k that is unmarked # and set k to this new value until k^2 > N $found = $false; for ($i=$k+1;!$found;$i++) { if ($a[$i]){ $k = $i; $found = $true;} } } $t2 = new Benchmark; # 4. The unmarked numbers are primes $p=0; for ($i=2;$i<=$N;$i++) { if ($a[$i]) { print "$i\n"; $p++; } } print "$p primes, time> ",timestr(timediff($t2,$t1)),"\n";