Machine Organization I

V22.0201 - Fall 2002

Nathan Hull

Assignment III

Due: Thursday, October 24th

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: