Back to Project Euler

Previous Problem Next Problem

Problem 10: Summation of Primes

Solution

This is the most important problem on Project Euler.

A naïve approach, but one sufficient for this problem's cap, would be to generate a list of primes — perhaps with the sieve of Eratosthenes, as in Problem 7, or with a library function — and simply sum the list. For eight years after this problem was posted, all recorded solutions to this problem took such an approach.

Then, in 2013, a user by the name of Lucy_Hedgehog posted an improved algorithm. The issue with the sieve of Eratosthenes is that it takes \(O(n)\) space and \(O(n \log \log n)\) time. Lucy's ingenious method, which sums the primes without needing to find them all, takes \(O(\sqrt n)\) space and approximately \(O(n^{3/4})\) time, making it far more suitable for problems with higher caps.

Since her own description of the method is about as clear and concise as it gets, I'm just going to quote it here with some slight formatting changes:

Let \(S(v,m)\) be the sum of integers in the range \(\{2, \ldots, v\}\) that remain after sieving with all primes smaller or equal than \(m\). That is \(S(v,m)\) is the sum of integers up to \(v\) that are either prime or the product of primes larger than \(m\).

\(S(v, p)\) is equal to \(S(v, p-1)\) if \(p\) is not prime or \(v\) is smaller than \(p^2\). Otherwise (\(p\) prime, \(p^2 \leq v\)) \(S(v,p)\) can be computed from \(S(v,p-1)\) by finding the sum of integers that are removed while sieving with \(p\). An integer is removed in this step if it is the product of \(p\) with another integer that has no divisor smaller than \(p\). This can be expressed as

\[S(v,p) = S(v, p-1) - p (S(v/p, p-1) - S(p-1,p-1)).\]

Dynamic programming can be used to implement this. It is sufficient to compute \(S(v,p)\) for all positive integers \(v\) that are representable as \(\lfloor n/k \rfloor\) for some integer \(k\) and all \(p \leq v\).

On Project Euler, users who've solved a problem can post their solutions in a private thread, and can provide "kudos" to the posts of other solvers. It's exceedingly rare for posts after the first page to get more than 20 kudos. Lucy's is on the fifth page, and as of time of writing, it has 495.

Sublinear number-theoretic summation is a common thread among the most challenging problems on Project Euler. Lucy's algorithm, and the ideas behind it, are absolutely essential to understand in order to tackle those problems.

If you're interested in learning further, my friend Griff has a great blog post about implementing Lucy's algorithm with Fenwick trees.

Python Code (also quoted directly from Lucy's post)

def p10(n=2000000):
	r = int(n**0.5)
	assert r*r <= n and (r+1)**2 > n
	V = [n//i for i in range(1,r+1)]
	V += list(range(V[-1]-1,0,-1))
	S = {i:i*(i+1)//2-1 for i in V}
	for p in range(2,r+1):
		if S[p] > S[p-1]:  # p is prime
			sp = S[p-1]  # sum of primes smaller than p
			p2 = p*p
			for v in V:
				if v < p2: break
				S[v] -= p*(S[v//p] - sp)
	return S[n]

Previous Problem Next Problem

Back to Project Euler