Project Euler — problem 10

[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.

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 their blog: Tony's bubble universe » R.

R-bloggers.com 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)