**Problem:** What is the 10001st prime number?

**Commentary:** So it’s finally time to discuss my prime-searching algorithm, as promised back in Problem 5. We will find primes in the following way:

- 2 and 3 are prime
- We examine the odd integers (having already discovered the only even prime) starting with .
- First, check if is of the form for some integer . If so, then can’t be prime, because then , and since , (so ). In this case, don’t even bother proceeding; replace with and start over.
- Calculate . Among all known primes below (going no further for the same reason as that outlined in Problem 3), check if these primes divide into . If we find one that does, then there is no reason to proceed; is not prime. Go back to 3. and try again with replced with . If none of the known primes below divide , then stop; must be prime. Add it to the list of known primes.
- Repeat this process by replacing with until we have 10001 primes.

It’s nothing fancy, but it works. As for the implementation, believe it or not, I actually don’t construct a list of length 10001 and insert into it as I gather my primes like a good little R user. See the post-code commentary for an explanation.

**R Code:**

ElapsedTime <- system.time({ ########################## primes <- c(2, 3) i <- 3 while (length(primes) < 10001){ flag <- 0 i <- i+2 if (i%%6 == 3){ flag <- 1 } if (flag == 0){ s <- sqrt(i)+1 for (prime in primes){ if ((i%%prime == 0)){ flag <- 1 break } if (prime > s){ break } } if (flag == 0){ primes <- c(primes, i) } } } answer <- tail(primes, 1) ########################## })[3] ElapsedMins <- floor(ElapsedTime/60) ElapsedSecs <- (ElapsedTime-ElapsedMins*60) cat(sprintf("\nThe answer is: %d\nTotal elapsed time: %d minutes and %f seconds\n", answer, ElapsedMins, ElapsedSecs))

**Output:**

The answer is: 104743

Total elapsed time: 0 minutes and 1.191000 seconds

**Post-Code Commentary: **You may notice that I’m not pre-allocating the prime list and then storing new prime values as I go, like a good little R user. The reason is that it’s actually slower to do it this way. Now maybe I’m an idiot and I don’t really understand how R does things, but if I take this algorithm and only modify the prime storage part of it to include preallocating the list and then injecting into that list (replacing a 0) as I go, then the time is nearly *a full order of magnitude* slower. Here’s the R code that you would produce if you were to do what I just described:

primes <- numeric(10001) primes[1:2] <- c(2, 3) i <- 3 prime.position <- 3 while (primes[10001] == 0){ flag <- 0 i <- i+2 if (i%%6 == 3){ flag <- 1 } if (flag == 0){ s <- sqrt(i)+1 for (prime in primes[primes > 0]){ if ((i%%prime == 0)){ flag <- 1 break } if (prime > s){ break } } if (flag == 0){ primes[prime.position] <- i prime.position<-prime.position+1 } } } answer <- tail(primes, 1)

So how do the two run? Well, on my work computer (which is a little slower than my home computer–also don’t tell my boss!), the original “bad R user” code runs in 1.852 seconds. The “better” solution with pre-fetching the vector runs in 11.100 seconds. That is a 9.248 second differential, which amounts to a nearly 500% increase in run time!

Of course, there are plenty of times when it’s objectively better to pre-allocate; but as it turns out, this isn’t one of them (though I have no idea why).

August 19th, 2011 at 12:55 pm

[…] solution, namely in the prime-y stuff; however, I don’t really want to get into that until Problem 7. So I […]

August 26th, 2011 at 11:53 pm

[…] we’ll be using that old prime algorithm I’ve already discussed to death. Other than a few tricks in there that I never see get […]

October 27th, 2011 at 6:21 pm

[…] we'll be using that old prime algorithm I've already discussed to death. Other than a few tricks in there that I never see get […]

October 28th, 2011 at 10:36 am

[…] in this solution, namely in the prime-y stuff; however, I don't really want to get into that until Problem 7. So I […]