"Robert J. Kolker" wrote:

Trey Jones wrote:

Even primes seem abstractly possible.. The Sieve of 
Archimedes (was it Archimedes?

Sieve of Eratosthenes.

In the mid 80's, I wrote my first Pascal program.  Using a 
popular benchmark as a guide, I implemented the Sieve of 
Eratosthenes on an IBM XT ... it ran 100 x faster than that 
benchmark implementation which was written in BASIC.  

Here is my implementation ... 

PROGRAM primenumbers (input, output);
  CONST
    firstprime = 2;
    maximum = 32767;
  VAR
    sieve : PACKED ARRAY [firstprime .. maximum] OF boolean;
    leftin, range, factor, multiple : LongInt; {0..maximum;}
  BEGIN
    Write ('Enter range: ');
    read(range);
    FOR factor := firstprime TO range DO
      sieve[factor] := true;
    leftin := range - firstprime + 1;
    factor := firstprime - 1;
    REPEAT
      factor := factor + 1;
      IF sieve[factor] THEN { factor is prime }
        BEGIN
          write(factor:7, ' ');
          multiple :=1;
          WHILE factor * multiple <= range DO
            BEGIN
              IF sieve[factor * multiple] THEN { remove multiple }
                BEGIN
                  sieve[factor * multiple] := false;
                  leftin := leftin - 1
                END;
              multiple := multiple + 1
            END { while }
        END
    UNTIL leftin = 0;
  END. { primenumbers }

Eratoshtenes was a very clever man who ran the Library at 
Alexandria.  Among his accomplishments was the measurement 
of the circumference of the Earth to within 5 percent of 
its modern value.

He also proposed that a leap day be added every fourth 
year to keep the seaons in line with the months.

http://scienceworld.wolfram.com/biography/Eratosthenes.html

Bob Kolker

Thanks for the info.  

-- 
Martin G. Diehl

Reality -- That which remains after you stop thinking 
about it.  

All replies and comments accepted and considered.  
Adoption of your suggestions are at my sole discretion.  
Award criteria are unpublished and are considered to 
be a trade secret.  As such, awards for your responses 
cannot be guaranteed.  Incoming flames may be stored 
for use during severe winters or may be circulated for 
deep analysis, peer review, and/or literary criticism.