SPUG: Sophistry Re: Primes

[Fred Morris]

Eratosthenes clearly calls out the procedure for his Sieve and you have to 
allocate the entire range and then you mark them off... yes/no, yes/no...

Here, the limit could be dynamic: the algorithm consumes the resources it 
needs, when it needs them. The Sieve, while it may be conceptually posited as 
a story to understand what is going on here, never exists at one point in 
space/time: you might see it with appropriate time-lapse photography. In 
reality though the holes appear as we learn something about them and 
disappear as we pass them.

In the case of the actual Sieve, the "holes" are dumb. Here the "holes" tell 
you their factors.

Notwithstanding the foregoing, an important observation which applies to 
Sieves does apply here.

1) When we find a prime P, the first hole we need to tell about it is P 
squared. This means that the holes no longer have a complete list of (prime) 
factors as it did in the naive version, but a hole H still contains a list of 
all factors <= sqrt(H), which is sufficient to compute the complete list of 
factors with little difficulty.

2) The limit still can be utilized as a hint for some optimizations. Once we 
get past the square root of the limit, a prime is still a prime but we don't 
need to post it forward because it's past the limit.

(Here, without the subroutine... although I still feel more comfortable making 
sure something exists before I attempt to do something with it.)

(Why the map in void context? A Pythonism or something, I guess.)

(Is this the best way to find primes? Wot, you're gonna use Perl to find 
primes?)

#!/usr/bin/perl

use Getopt::Std;
use vars qw/ %Options /;
use strict;
#use warnings;

getopts('p:t', \%Options );

my $limit = $Options{p};
($limit =~ m/^\d+$/) or die 'p must be an unsigned decimal integer';
my $truncate = exists $Options{t} ? sqrt($limit) : $limit;

my $i = 2; # First possible value.
my %numbers;

while ($i < $limit) {

    if (exists $numbers{$i}) {
        map push( @{$numbers{$i+$_}},$_), @{$numbers{$i}};
        delete $numbers{$i};
    }
    else {
        printf "%8d\n", $i;
        push( @{$numbers{$i*$i}},$i) if ($i < $truncate);
    }

    $i += 1;
}

exit(0);

__END__

Fred Morris