This is problem 10 on Project Euler: https://projecteuler.net/problem=10
In this problem, we are tasked with finding the sum of the primes below 2 million. This means we have to implement a method for finding prime numbers below a given integer.
The Sieve of Eratosthenes is a basic (read: easy to implement) and fast algorithm for finding prime numbers.
This makes our task boil down to just two steps:
- Step 1: Write a method that will return a list of prime numbers below an integer n
- Step 2: Write a method that will sum up all the numbers in a list
And voila! You're done.
We got burned in a prior problem using 32-bit int instead of 64-bit long, so make sure you use long. 2^32 ~ 2^30 ~ 1000^3 ~ 1 billion, and we're almost surely going to be seeing numbers larger than 1 billion. (If we were summing up all the integers below N, we would expect a result of ~N^2). This is a hyperconservative assumption, as prime numbers occur much less frequently than integers.
This leads to some interesting side questions: what, exactly, is the frequency of occurrence of prime numbers? It turns out that the probability of a number x being prime grows with the value of x as
Project Eulerproject euler notes
Round 1: Problems 1-20
Round 2: Problems 50-70
Round 3: Problems 100-110
Round 4: Problems 500-510
Round 5: Problems 150-160
Round 6: Problems 250-260
Round 7: Problems 170-180