"The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million."
Here is my current code
right now my loop that runs 2,000,000 times seems to be a bit much for java to handle because it freezes around the 90,000 range. How can I improve my code and get it to work? Thanks.
Now, whether or not there is an algorithm that would specifically speed up the Euler calculation I don't know.
Other than 2, they are all odd. So, no sense testing each and every number up to 2M. Give some thought to skipping over even numbers. Then, give some thought to never testing x%2.
(If you have learned about arrays) You may want to make some small scale experiments - the limit being 10K, for example - to observe that for any modulo of zero, the operands can never be a number already shown to be not prime. That is, in the 2,3,5,7,11,13 sequence, the next test is for 15. So, no sense testing 15%4 because 4 has already been discarded as not prime, being a multiple of 2.
Then, 15%5 is zero and we discard 15. Any number discarded is known to be a multiple of an even lower number.
Then, 17. Working through an array of known primes, we find no solution. Same for 19.
Then, 21. Working through an array of known primes, we find 3 as a solution, so discard 21.
How about 323? Testing 323%17 is a solution, so discard it. The point here is that the inner loop only went seven iterations instead of seventeen.
It took about 1.1s to set up a Sieve with 20,000,000 elements, about 0.6s to use a Stream which interrogates the Sieve and 3½min using isProbabePrime. My current computer is very slow at times.
John Sing wrote:right now my loop that runs 2,000,000 times seems to be a bit much for java to handle because it freezes around the 90,000 range. How can I improve my code and get it to work? Thanks.
OK, well first off, your line 10 check is extremely wasteful. You don't have to check all divisors from 2 to x or even close.
Second: You only need to check prime divisors, because if the divisor - y in your program - is composite (ie, not prime), and
x % y == 0
then x must ALSO divide exactly by y's divisors. And since you're building up a list of primes anyway, why not just re-use it?
Third: As Carey suggested, it's probably worth making division by 2 a special case, since it eliminates so many "candidates" immediately.
pointing OP to the 'Sieve' is as far as I would go.
The whole point of Project Euler is to find out:
1) what exactly the problem is
2) then determining if brute force is applicable or not
3) having determined the method to use, how to implement it
4) optimizing comes only after solving it and seeing how fast all these Python guys/girls did it
So pleae don't give code.
Piet Souris wrote:pointing OP to the 'Sieve' is as far as I would go. ... So please don't give code.
I agree with you in general, but most of what Campbell and Carey were showing was specifically a Stream-oriented solution, which is specific to version 8.
TBH, I reckon that this is one thing that Streams probably aren't the best for - although I have to admit I rather like the idea of an open-ended PrimeStream class...
The whole idea of Project Euler is to make people think about algorithms; you are supposed to find an efficient algorithm for finding prime numbers. Creating a sieve of Eratosthenes with an array or (good idea whoever said that) a BitSet is probably much faster than testing each number for primeness. Also remember you do not have to iterate the whole range, so your sieve creating algorithm doesn't run in quadratic time.
Winston Gutkowski wrote:. . . OK, well first off, your line 10 check is extremely wasteful. You don't have to check all divisors from 2 to x or even close.
You do not need to check all of them. A little thought will allow you to reduce your search space greatly.
. . . You only need to check prime divisors, . . .
Campbell Ritchie wrote:The whole idea of Project Euler is to make people think about algorithms; you are supposed to find an efficient algorithm for finding prime numbers. Creating a sieve of Eratosthenes with an array or (good idea whoever said that) a BitSet is probably much faster than testing each number for primeness.
It seems to me that we're mixing up all sorts of things in this discussion:
1. The requirement - which is to return the sum of primes less than 2,000,000.
2. The algorithm - which presumably means the best one for getting ALL primes less than 2,000,000 - unless there is an alternative way of getting a sum which doesn't involve getting them all.
3. The implementation - which may or may not be best with a BitSet or any other data structure.
John asked us to critique his code which - and here I agree with Piet - we have signally failed to do.
Let's stick to the question.
Winston Gutkowski wrote:John asked us to critique his code which - and here I agree with Piet - we have signally failed to do.
Yes, we've had a drunken weave off of the original post, but there were a number of optimizations suggested that would speed up the OP code incredibly. I went back to the OP code and massaged it with the suggestions plus one that was hinted at and I was able to get the sum in 240 milli-seconds, vs my 20 milli-seconds for the sieve (admittedly I have a fast machine).
To summarize the suggestions:
The maximum gap between two known primes so far discovered is 1,476 (between two 18 digit numbers) - and I'm sure it'll be beaten soon - but AFAIK we still don't even know how to calculate what the maximum gap is, let alone how to prove that two known primes are adjacent (beyond brute force).
The whole area seems to be riddled with conjecture - including Legendre's (which AFAIK has yet to be proven) - and yet we continue finding all sorts of "spirals" and patterns and other useful stuff while we're searching.
Good old Maths.
Carey Brown wrote:
Hint: what's the maximum possible prime you need to check for any X?
I can't think of a way off hand to guide you to the hint without just coming out and saying it, but is much less than half of X.