// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 10 Solution

Project Euler 10 Solution

Project Euler 10: Calculate the sum of all the primes below two million


Project Euler 10 Problem Description

Project Euler 10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Analysis

Project Euler 10This problem requires us to generate 2 million prime numbers, sum them and report their total. Using our prime number sieve introduced in problem 7 this is easy to solve in less than 100ms with a couple lines of Python:

from Euler import prime_sieve
print sum(prime_sieve(2000000))

HackerRank asks a much more demanding question by having us solve up to 10,000 trials for any N≤1,000,000. Even though the prime number range is halved, it still requires both prime and non-prime queries up to N. This can be trickier than first thought and required a more utilitarian solution. Having the possibility of non-prime queries means that simply mapping prime numbers to sums won’t work in those cases, especially with the time restriction.

This solution sieves the primes and calculates a running sum concurrently before accepting any queries by filling a list (prime_sum) with those sums. This allows each query to act as an index to the appropriate sum in the list.

Project Euler 10
This program and method
solves all test cases for
Project Euler 10 on HackerRank

Project Euler 10 Solution

Runs < 0.310 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 10 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|142913828922|

Afterthoughts

  • Function prime_sieve is listed in Common Functions and Routines for Project Euler
  • Prime numbers are used often for solving Project Euler problems and the prime sieve provided here is much faster than traditional methods.
  • There are better ways to select candidates for being composite or prime, such as checking only odd numbers, but that understanding simply wasn’t implemented.
  • This example only solves N≤10,000 because the Trinket is slow.
Project Euler 10 Solution last updated

Discussion

No comments yet.

Post a comment