Project Euler — problem 7

June 6, 2012
By

(This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers)

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
1
2
3
4
5
6
7
8
9
10
11
12
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 his blog: Tony's bubble universe » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.