Project Euler #10: Summation of primes

This post is copied from another blog I run. I'll be shutting that blog down shortly and all future posts of that kind will go on this blog. These are solutions to various programming brain teasers. Optimizing your solution is the real challenge.

The problem reads as follows:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

Right from the start I can think of two methods:

1. Using a similar solution as for PE-7 but adding the primes instead of storing them
2. Sieve of Eratosthenes

I opted for the first method since I'm lazy. With minimal modifications, I get 173518 microseconds as my runtime. I was curious about the second method, so I copied and modified a solution found in the problem discussion thread. You can find that one under sieve.cpp. It has a runtime of 221631 microseconds. That's still pretty good.

The third way I can think of is to combine the first two methods. As with PE-7, automatically exclude all multiples of 2 and 3 for a 2/3 reduction in numbers considered. Then find all the primes below the square root of 2 million (so anything below and including 1415) and sieve on the remaining 1/3 with those prime numbers. Could result in a nice speedup over the first method. As usual, another thing you could do is to remove the use of the modulus operand - it's expensive.

The code can be found here 

Installing libclc on Ubuntu 14.04 LTS

libclc is needed for using Clang with OpenCL. See here for more details. Unfortunately it requires LLVM to be 3.7 or higher, while Ubuntu 14.04 only has up to 3.6.

Make sure you don't have LLVM installed before proceeding.To get around this you first have to get LLVM 3.7 by adding this line:

deb http://llvm.org/apt/precise/ llvm-toolchain-precise-3.7 main

 to this file:

/etc/apt/sources.list.d/llvm.list

I used nano. The original instructions using output redirection didn't work for me. You can find the address for other versions of Ubuntu or LLVM here. Now install llvm-3.7 and clang-3.7

sudo apt-get install llvm-3.7 clang-3.7

It will complain that it can't verify the source, but we added the source so go ahead and ignore it. Next get libclc if you don't already have it:

git clone http://llvm.org/git/libclc.git

Go through the readme and use llvm-config-3.7 instead of llvm-config. You may get an error like so:

/usr/bin/ld: cannot find -ledit

In this case just install libedit:

 sudo apt-get install libedit-dev

 However I still got many warnings of the following type:

WARNING: Linking two modules of different data layouts: 'amdgcn--/lib/image/write_image_impl.ll.tahiti.bc' is '' whereas 'llvm-link' is 'e-p:32:32-p1:64:64-p2:64:64-p3:32:32-p4:64:64-p5:32:32-p24:64:64-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64'

A quick google search returned nothing. Because the data layout of the first module is empty I'm going to proceed with the assumption that I can ignore this.