Sieve of Eratosthenes

Today I’ll be discussing a way to find all primes up to a certain number using the Sieve of Eratosthenes. The algorithm is useful for many Project Euler problems and it was an interesting challenge to code in R.

1
2
3
4
5
6
7
8
9
10
SieveOfE <- function(n) {
 primes <- rep(TRUE, n)
 primes[1] <- FALSE
 last.prime <- 2
 while (last.prime <= sqrt(n)) {
   primes[seq.int(2*last.prime, n, last.prime)] <- FALSE
   last.prime <- last.prime + min(which(primes[(last.prime + 1) : n]))
 }
 which(primes)
}

I created a function named “SieveOfE” which takes the input of a number and returns all primes up to that number. After inputting a number, “n”, the function creates a logical vector that is “n” in length with “TRUE” in every position. It then manually sets the first spot to be “FALSE” and defines the last prime to be 2.

This is where the efficiency of this algorithm shines. The function then goes through and eliminates all multiples of the last prime (2 for the first iteration) by making their positions’ values “FALSE”. The next “last.prime” is then chosen by first generating a sub-vector from the “primes” vector of all those values that are still “TRUE” (starting from 1 + the previous prime used) and finding the minimum of that vector (this will find the minimum position relative to the previous last prime rather than the actual next prime number, which is why we add this value to the last prime to get the new “last.prime” variable).

This process is repeated until “last.prime” is less than or equal to the square root of the input number (this greatly optimizes the function). Finally, the function outputs which values in the “primes” vector are still true.

1
2
3
4
5
> SieveOfE(100)
[1]  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

   user  system elapsed
   0.02    0.02    0.01

As you can see, this function is lightning quick.