Project Euler — problem 10

June 15, 2012
By

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

Just finish my last assignment for this week. IT’S WEEKEND, officially. Let me take a break to have a look at the tenth problem, another prime problem. It’s no doubt that prime is the center of the number theory and fundamental to arithmetic. No wonder there are so many prime problems in Euler project. Well, enough chatting. Here is the tenth problem.

Find the sum of all the primes below two million.

Simple, right? Pick all the primes, then sum up. In the solution of problem 3, I have used a helper function is.prime() to check the primality, which could also be applied here to test each number below 2e6. However, the trial division is kinda slow. To check on all numbers under a given limit N, it is a O(N) algorithm (am I right ? T(N) = (sqrt(N) + 1) * sqrt(N) / 2). An efficient algorithm such as Sieve of Eratosthenes would help a lot. I write a helper function PrimeSieve(limit) to generate all prime numbers under a given limit.

?View Code RSPLUS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
PrimeSieve <- function(n) {
  if (n <= 1) {
    primes <- numeric(0)
  }
  if (n == 2 | n == 3) {
    primes <- 2:n
  }
  else {
    numbers <- 2:n
    sieve <- rep(TRUE, times = n - 1)  # let all flags to be TRUE
    cross.limit <- floor(sqrt(n))
    count <- 1   
    p <- numbers[sieve][count]  # let p be the first sieve number
    while (p <= cross.limit) {
      sieve[p * (2:floor(n / p)) - 1] <- FALSE
      count <- count + 1
      p <- numbers[sieve][count]
    }   
    primes <- numbers[sieve]
  }
  return(primes)
}
result <- sum(as.numeric(PrimeSieve(2e6)))
cat("The result is:", result, "\n")

This solution is much efficient. It saved me 9/10 of running time, compared with the solution using trial division. And one more thing : one can use gmp::isprime() function for primality check. Compared with my PrimeSieve(), it’s a little faster, I admit. But just a little, about 2.5 seconds :p

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.