Machine Organization I

V22.0201 - Fall 1996

Nathan Hull

Assignment II

Due: Thursday, October 24

Sieve of Erasthosenes Prime Number Generator

This algorithm generates prime numbers between 2 and N.

1) Put the value of N in a word dw called NUM (e.g. 1027 decimal). You may either read this in using an INT, or place it in by hand using the debugger.

2) Compute the value of the integer sqrt (n) using the method we created in class. (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. Place this in the DS segment for 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.

6) Run your program twice, once for the value 31 decimal, and once for 1027 decimal. Output the count to the screen and print it, and also print the Turbo debugger screen showing the first sixteen bytes of the db table PRIMES.

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