The sieve of Eratosthenes is an algorithm to enumerate all prime numbers smaller than a given number . It uses a table with entries for each number from 2 to  and successively marks numbers in that table that are not prime. In the beginning, no table entry is marked.

To implement the table, we will use an array. An array is a data structure that stores a list of elements by putting them one after another in memory. Here, the list is the table of entries of 0 and 1 to indicate that a number is marked. Arrays have the appealing property that we can address an element in constant time by simply computing its address: If is the address of element 0, we can simply compute the address element  by where  is the size of an element in bytes (of course all elements have to be of the same “type” and therefore have to have the same size in order for this to work).

Note that we will use an array from  to  because it makes indexing simpler at the expense of two unused entries (0 and 1).

The idea of the algorithm is simple: We look at each number from 2 to  successively. If number  is not marked yet, we mark all its multiples smaller than . For example, assume . When looking at table entry 3, we need to mark 6, 9, 12. All numbers not marked are prime.

Let’s think about why this algorithm is correct. If we arrive at  we know, because we considered all numbers smaller than  before, that the multiples of each number  have been marked. So if  is unmarked, it means that it does not divisible by any number bigger than 1. Therefore, is prime.

The marking process can be sped up by the following observation: All multiples of  that contain a prime factor  less than  have already been marked when we considered . So the smallest unmarked number is  and it is sufficient to start marking there. Consequently, there is no sense in marking multiples of a number  with .

Analyzing the running time of the optimized procedure is interesting. Let  be the greatest integer such that . For each  we are marking all multiples greater or equal to  and smaller than . So the overall number of markings performed is

In the last step, we have exploited that is an upper bound to the -th harmonic number .

Let us finally give the implementation of the sieve of Erastothenes in RISC-V assembly:

    .text
eratosthenes:
    .globl eratosthenes
    sub   a2, a1, a0
    mv    t0, a0

    # initialize tables with 0s
    j      zero_check
zero_loop:
    sb     zero, 0(t0)
    addi   t0, t0, 1
zero_check:
    bne    t0, a1, zero_loop

    # we start with q=2
    li     t0, 2
era_loop:
    mul    t6, t0, t0  # marking starts at q*q
    bge    t6, a2, end  # we don't need to mark
                        # if q*q > N
    add    t1, a0, t0  # compute address of entry q
    lb     t1, 0(t1)    # load entry
    bne    t1, zero, no_prime # if marked, no prime, no marking

    # here, q (in t0) is a prime
    # mark all multiples of q beginning from q*q
    add    t1, a0, t6  # compute address of entry of q*q
    li     t5, 1        # put a 1 into a register
    j      mark_check
mark_loop:              # loop to mark all multiples
    sb     t5, 0(t1)
    add    t1, t1, t0
mark_check:
    blt    t1, a1, mark_loop

no_prime:
    addi  t0, t0, 1    # set t0 to q + 1
    j      era_loop
end:
    ret