Project Euler/10: Difference between revisions
From charlesreid1
(Created page with "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...") |
No edit summary |
||
| Line 11: | Line 11: | ||
And voila! You're done. | 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. | 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 | |||
<math> | |||
\dfrac{1}{\ln{(x)}} | |||
</math> | |||
{{ProjectEulerFlag}} | {{ProjectEulerFlag}} | ||
Revision as of 09:15, 1 July 2017
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)}} $
