Project Euler/10

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

${\dfrac {1}{\ln {(x)}}}$