Index to Solutions to Eratosthene's Sieve


      This directory describes a neat way to list prime numbers that uses a large number of concurrent communicating processes. [ Specification ]

      The solution lends itself to coding in Ada (using rendezvous), Smalltalk (using filters and recursive messages), C using semi-coroutines, and C using a pipe. Examples of these solutions are in this directory. Also there are solutions in Smalltalk, C++, Java.

      The Prolog code shows a version that is close to Eratsostene's original concept of listing a lot of numbers and crossing out the non-primes.


      Ada using rendezvous and a task type. [ sieve.ada ]

      Unix Shell

        This directory has the components necesary to experiment with this in Unix:
      1. p0sh n - generate 2,3,4,5,...n [ p0sh ]
      2. ppsh - save first and remove all multiples. [ p1sh ]

        In theory an infinite pipe like this forms the sieve:

      3. p0sh|p1sh|p1sh|p1sh|p1sh|... In practice you don't need many filters to get a lot of primes: [ sievesh ]

        Unix Shell and C

        You can of course code the two shell scripts into C: [ p0.c ] [ p1.c ] and then compile them into p1 amd p2 and use them in place of p0sh and p1sh.

      . . . . . . . . . ( end of section UNIX Shell) <<Contents | End>>


      C using restartable code or a semi-co-function [ sieve.c ]


      C++ via a class of Primes. [ sieve.C ] (older) and [ sieve.cpp ] (newer).


        Simple Sieve

        A simple version defining a Filter interface: [ ] and documentation [ Sieve.html ]

        Co-Routine Style

        Here is an example of programming Java Threads to work like co-routines (only one runs at a time, with flow weaving between the individual threads) It prints out some helpful diagnostics as it runs. See the code [ ] plus documentation [ ThreadedSieve.html ]

        It is possible to develop a reusable class of SemiThreads that run as co-routines [ SemiThread.html ] and then derive Hoare's Prime as a special extension: [ PrimeThread.html ] Working out the Java code is left as an exercise.


        Java provides some ready-made synchronization primitives: wait(), notify(), and yield(). The use of these is shown in: [ ../java/ ] with documentation in [ ../java/DataThread.html ] and [ ../java/PrimeThread2.html ]

        An untested generic DataThread can be found in: [ ../java/ ] Does it work?


        Java has a low level version of the UNIX pipe that is ideal for buffered message passing between threads. Each pipe has two ends: a PipedInputStream and a PipedOutputStream. The pipe is created by connecting these together. See the code [ ] and documentation: [ PipedSieve.html ] [ PrimeFilter.html ] and [ Filter.html ]

      . . . . . . . . . ( end of section Java) <<Contents | End>>


      Smalltalk using filters and generators: [ ]


      Why not take this same concept and map it onto one of out GPU systems?

      Other Prime Number Generators


      Prolog using a dynamic database of primes: [ sieve.plg ]

      C [ ../c/primes.c ] LISP [ ../lisp/primes.lsp ] Prolog [ ../prolog/primes.plg ] [ ../prolog/primes2.plg ] Ada [ ../sebesta/primes0.ada ]

    . . . . . . . . . ( end of section Index to Solutions to Eratosthene's Sieve) <<Contents | End>>