The sieve of Eratosthenes is an ancient procedure for generating prime numbers (integers greater than 1 whose only divisors are themselves and 1). The sieve is initialized with a list of all integers greater than 1. Then, repeatedly, you:
- Pick the smallest non-crossed-out integer, n. This is the next-largest prime.
- Cross out all multiples of n.
The result “sieves” out the primes.
Let’s model this with pipes!
1. Write a shell command that writes to standard output all integers greater than 1, one per line. You may write a C++ program if you can’t find an appropriate shell utility. (This is the initialization step.)
2. Write a shell command that reads a list of integers on standard input, one per line, and writes to standard output those integers that are not multiples of n, a number specified on the command line. You may write a C++ program if you can’t find an appropriate shell utility. (This is the crossing-out step.)
Hint: Check out the
awkprogram, and especially its
3. Your goal is to write a program,
primesieve, that uses your answers to
#1 and #2 and pipes to create a sieve of Eratosthenes. First, draw some
pictures of the sieve in different stages—for instance, after the
initialization step; after the first crossing-out step; and after three
4. Write C++ code to add another filter (i.e., crossing-out step) to the sieve.
5. Write the sieve!
Our solutions for
primesieve are stored in
cs61-lectures/process8/sol/primesieve.cc. After trying to do this problem
yourself, check out our solutions:
$ cd cs61-lectures/process8 $ cp sol/* . $ make $ ./primesieve | less
Read the code too. It’s very important that
./primesieve not buffer its
standard input; why?
This will create a huge number of helper processes; for example:
$ ./primesieve 2 3 5 7 11 ... [after running a while]... $ pstree -p bash─┬─primesieve─┬─168*[filtermultiples] │ └─seq └─pstree
But if you kill
primesieve, all the helper processes will die too!
$ killall -9 primesieve Terminated $ pstree bash───pstree
Why? Because of
SIGPIPE, the signal delivered when a program writes to a
pipe with no open read ends. After
primesieve is terminated, the previous
filtermultiples 997) will eventually make a
system call to its standard output. The operating system responds with
SIGPIPE because the corresponding pipe’s read end is closed. Then
filtermultiples 997 is terminated. That closes the read end of the
previous pipe, so eventually the previous
filtermultiples 991 is
terminated in a similar way. The terminations ripple back all the way through
the pipeline and everything cleans itself up.