Sieve of Eratosthenes

C Program

In your MingGW environment, copy msieve.c and msieve.exe to a directory on your MSYS system as per the last homework question. Run the program under MSYS using different inputs such as "./msieve.exe 20".

Sieve Algorithm

The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to a given number n. In our version, we will sieve using a bit array in which one bit is used to represent each number. The bit array is represented in the array a[] of msieve.c. Since it is a bit array, a single byte is used to represent 8-bits. Assume an array of bits is initialised all to 1's and called "a[]" (we cannot represent arrays of bits in standard programming languages). The algorithm starts with a counter i being equal to the first prime 2, and crosses off all multiples of 2 (i.e. 4, 6, 8 ..) by setting the corresponding bits in the bit array to 0. It then finds the next non-zero number which is 3, and crosses off all multiples of 3 (i.e. 6, 9, 12 ...). It then finds the next non-zero number which is 5, crosses off 5, 10, 15 ... and continues until (i*i <= n). After this, the remaining set bits greater than or equal to 2, are the prime numbers between 2 and n.

This nice applet demonstrates the algorithm.

Homework Problem

Write an IA-32 assembly language program that can be linked with msieve.c to produce your own working sieve program. If you call your assembly language program "sieve.s", it can be assembled and linked with msieve.c using the following sequence of commands under msys:
as -o sieve.o sieve.s
gcc -o sieve sieve.o msieve.c

Note that in msieve.c, we assume that the elements of the bit array are in a certain position and your solution must work with the supplied msieve.c. Marks will be awarded as follows:
50%: correctness, must produce the correct result up to the maximum value of n (i.e. LARGEST_N in msieve.c)
30%: readability, more marks will be awarded to well written and well commented programs
20%: performance, although we will not award any extra marks for performance, we will deduct marks if a particularly inefficient solution is submitted.