Sieve of Eratosthenes

Your MIPS assembly program is to determine the number of prime numbers in a given range of values using the simple, ancient algorithm proposed by the Greek mathematician, Eratosthenes around 200 B.C.

The algorithm is described in a questionable source as follows:

A prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),
2. Initially, let p equal 2, the first prime number,
3. While enumerating all multiples of p starting from p², strike them off from the original list,
4. Find the first number remaining on the list after p (it's the next prime); let p equal this number,
5. Repeat steps 3 and 4 until p² is greater than n.
6. All the remaining numbers in the list are prime.

Use your assembly program to determine the number of prime numbers in the range from 0 to a value entered by the user. Make sure that you inform the user of the limits of your programs ability.

Example Run

Please enter the maximum value to be tested for prime numbers: 15000

In the range of 1-15000, the number of primes is: 1754

Program terminated.