Project Euler — problem 7

[This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Prime is the core of number theory. Here is an introduction of prime number on Wikipedia. I could only understand roughly half of it. Now, let’s look at the seventh problem of Project Euler, which is another about prime number. 

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?

To find out the 10, 001st prime number, there is no shortcut, I think. One can set a counter and test the primality of each natural number from 1. Meet a prime, counter plus one; meet a composite, move on.
Here I use a faster alternative method to solve this problem. I also test the primality using trial division, but I store the prime numbers in an array (a numeric vector in R). Then I use this list of primes to test whether the next natural number is a prime or not. I start with two prime number, 2 and 3, and only check the primality of odd numbers.

?View Code RSPLUS
n <- 10001
prime.seq <- numeric(n)
prime.seq[1:2] <- c(2, 3)
candidate <- prime.seq[2] + 2
for (i in 3: n) {
  while (any(candidate %% prime.seq[1:(i - 1)] == 0)) {
    candidate <- candidate + 2
  prime.seq[i] <- candidate
  candidate <- candidate + 2
cat("The result is:", prime.seq[n], "\n")

Within the code above, the while loop is used to test the primality. If the candidate number can’t be divided without remainder by the prime numbers smaller than itself, the while loop stops and the candidate is added to the prime list; otherwise the loop go on to test the next number. And the for loop works as the counter. Stop the program when encountering the 10,001st prime number.

To leave a comment for the author, please follow the link and comment on their blog: Tony's bubble universe » R. offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)