## Machine Organization I

## V22.0201 - Fall 2003

**Assignment IV**

*Due: Dewar's Section: Wed., Nov. 12; Hull's Section:
Thur, Nov. 13*

**Sieve of Erasthosenes Prime
Number Generator**

**This algorithm generates prime numbers between 2 and N.**

1) Read the value of N and put it into a word dw called NUM (e.g. 1027 decimal).
You should read this as a DECIMAL (ASCII) number from the keyboard.

2) Compute the value of the integer sqrt (n) using the method we demonstrated
in class from the Dewar book. (Sum of the first N integers = square of N.
The code is posted on the Web Site.) Put the square root in a *byte*
db called SQROOT.

3) Initialize an array of **bits** to zero. You must reserve a length
of N - 2. (Actually, (N-2) div 8 since memory is arranged in bytes only) Call
this table PRIMES.

4) With the leftmost bit of the first byte representing 2, the next
bit to the right representing 3, etc., and the second byte representing
the numbers 10, 11, 12, etc., inspect each location from 2 to sqrt (n).
If that location is still zero, turn on the bit in every multiple of that
location. Thus, since the two position is zero, you would "check
off" positions 4, 6, 8, 10, 12, etc., etc. (Note again that positions
10, 12, 14, and 16 are in the second BYTE of the array.) Then, you would
inspect position 3. Since it also is zero, you would "check off"
locations 6, 9, 12, 15, 18, etc., etc. Multiples of 4 would be skipped
since its bit is already set to one. When you have done this up to sqrt(n),
the positions which are still zero are the prime numbers 2 through N.

5) Count the positions 2 - N which are still zero. Put that number into a
word variable named COUNT, and print out that number to the screen in DECIMAL
(ASCII)

6) Go through the array, and print out all of the prime numbers in DECIMAL
(ASCII).

For example, with the input NUM set to 30, at the conclusion of the program,
memory should look like:

For the above example, the run might look like:

Input your number: 30

There are 10 prime numbers less than or equal to 30

They are:

2

3

5

7

11

13

17

19

23

29

**Additional points:**

1) Your program must be structured using procedures. This should be pretty
simple in this program: Possible procedures might include one for input, one
for output, one that prints a decimal number, etc.

2) Since you don't know how long your array needs to be, you might put it at
the END of your program so that it can grow to an sufficiently long length without
overwriting your code.