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.

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