Problem 7) 10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10,001st prime number?

Let us figure out approximately how many numbers that we need to search through. We know that the prime number function can be approximated by \(x/\log(x)\). Let us determine when this is greater than 10,001:

i=10000    # might as well start at 10000...
while (i/log(i) < 10000) {i <- i+1}
print(i)
## [1] 116672

Hence, the 10,001st prime should be less than 120,000. We will use the sieve of Erasthones technique. Our technique will be thus: define a vector equal to 2, 3, 4, 5,… up to 120,000. Set the “current prime” to be 2. We then use the selection function in R to exclude numbers that are multiples of 2 but not 2. This will leave us with 2, 3, 5, 7,… We then set our current prime to be the next prime, in this case 3. We exclude multiples of 3 but not 3 itself, i.e. 9, 15,… (the even multiples of 3 have already been eliminated). We continue up to where the current prime is no longer less than the square root of the top number.

Let’s not get greedy and start with a small sieve:

n.top <- 100
sieve <- 2:n.top 
p.current <- 2
while (p.current < sqrt(n.top)) {
  # eliminate multiples of p.current but not p.current:
  sieve <- sieve[ sieve %% p.current != 0 | sieve == p.current]
  # now we want to go to the next prime
  p.current <- sieve[which(sieve == p.current) + 1]
}
sieve
##  [1]  2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83
## [24] 89 97

It is interesting to look at how the length of the vector sieve shrinks at each step. The first step eliminates half of the entries.

n.top <- 10000
sieve <- 2:n.top 
length.sieve <- length(sieve)
p.current <- 2
while (p.current < sqrt(n.top)) {
  # eliminate multiples of p.current but not p.current:
  sieve <- sieve[ sieve %% p.current != 0 | sieve == p.current]
  length.sieve <- c(length.sieve,length(sieve))
  # now we want to go to the next prime
  p.current <- sieve[which(sieve == p.current) + 1]
}
plot(length.sieve)

Now, let’s look at the problem…

n.top <- 120000
sieve <- 2:n.top 
p.current <- 2
while (p.current < sqrt(n.top)) {
  # eliminate multiples of p.current but not p.current:
  sieve <- sieve[ sieve %% p.current != 0 | sieve == p.current]
  # now we want to go to the next prime
  p.current <- sieve[which(sieve == p.current) + 1]
}
sieve[10001]
## [1] 104743

Thus, the 10,001st prime is 104,743.