#
The Sieve of Eratosthenes

The goal of this assignment is to design a program which will
produce lists of prime numbers. The method is based on the one
discovered by
Erastosthenes
(276 - 196 BC). His method goes like this. First, write down a
list of integers
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Then mark all multiples of 2:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
x x x x x x x x x

Move to the next unmarked number, which in this case is 3, then
mark all its multiples:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
x x x x x x x x x x x

Continue in this fashion, marking all multiples of the next
unmarked number until there are no new unmarked numbers. The
numbers which survive this marking process (the Sieve of
Eratosthenses) are primes. (You should complete this marking
process yourself).
The new part of the C language that you will have to learn
in order to do this program is the **array**.

##
Problem 1

Design a program to make a list of primes less than N = 100
using Eratosthenes' method:
PSEUDOPROGRAM:
Set up an array of integers z[N]:
for i from 0 to N, set z[i] = i.
for i from 2 to N, mark all multiples
of i by setting them to zero
for i from 2 to N,
print all unmarked multiples.

Your program should be as short and elegant as possible, while
still being clearly understandable. Below is an outline for the
program
#define N 20 /* use small number for testing */
main(){
int z[N]; /* array of integers, z[0], ... z[N-1] */
for ( i = 0; i < N; i++ )
initialize z[i];
for ( i = 2; i < N; i++ )
mark the multiples of i;
/* this marking can be done with
one for and one if statement */
for ( i = 2; i < N; i++ )
print the unmarked entries of z;
}

##
Problem 2

Modifiy your program so that the output goes to a file.

##
Problem 3

Investigate the function
p(n) = Number of primes less than n

##
Problem 4

Investigate the infinite series
1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + ...

constructed by adding the reciprocals of the primes.

Back to syllabus

Back to Department of Mathematics, University of Utah

Last modified: Feb 21, 1995

Copyright © 1995 Department of Mathematics, University of
Utah