• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Liutauras Vilda
  • Knute Snortum
  • Bear Bibeault
Sheriffs:
  • Devaka Cooray
  • Jeanne Boyarsky
  • Junilu Lacar
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • salvin francis
Bartenders:
  • Tim Holloway
  • Piet Souris
  • Frits Walraven

Project Euler Question 10 help

 
Ranch Hand
Posts: 58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone I am trying to create a program to answer question 10 on Project Euler which is

"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.
 
Saloon Keeper
Posts: 6923
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To compute a list of "small" primes, the Sieve of Eratosthenes algorithm is the fastest. Much much faster than X%Y.
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Now, whether or not there is an algorithm that would specifically speed up the Euler calculation I don't know.
 
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(Not having looked at the project, nor any of the similar threads, nor aware of any other proven algorithm) There are some prima facie assumptions we can make about prime numbers.

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.
 
Carey Brown
Saloon Keeper
Posts: 6923
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dusted off my old sieve program.
Milli-seconds to compute primes up to 2,000,000 : 20
There are 148,933 primes
 
Marshal
Posts: 68066
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It might not be as quick to compute as a Sieve of Eratosthenes, but you can use a Stream.I shall leave you to go through the IntStream documentation and find out how many of those methods actually exist. If you have a Sieve array ready, you can use it from one of those calls in the stream to find whether the number is prime. I haven't found any isPrime methods but there is an isProbablePrime method in the BigInteger class.
 
Campbell Ritchie
Marshal
Posts: 68066
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I got the same result using a Sieve and using the BigInteger method, but the BigInteger technique is much slower. I think the isProbablePrime method is slow.
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.
 
Carey Brown
Saloon Keeper
Posts: 6923
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
 
Campbell Ritchie
Marshal
Posts: 68066
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I thought 144000 primes sounded rather too few. . . .
 
Carey Brown
Saloon Keeper
Posts: 6923
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With this code


I got this

Fill sieve: 20 milli-seconds
Filter LongStream: 60 milli-seconds
Total: 142,...

I was a bit surprised at how long the stream took.
 
Bartender
Posts: 10777
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.

HIH

Winston
 
Bartender
Posts: 3766
154
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Gents,

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.
 
Winston Gutkowski
Bartender
Posts: 10777
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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...

Winston
 
Campbell Ritchie
Marshal
Posts: 68066
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.

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.

. . . You only need to check prime divisors, . . .

You do not need to check all of them. A little thought will allow you to reduce your search space greatly.
 
Winston Gutkowski
Bartender
Posts: 10777
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
 
Carey Brown
Saloon Keeper
Posts: 6923
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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:
  • Treat '2' as a special case
  • Only process odd numbers
  • Only check numbers that were identified as primes previously
  • Hint: what's the maximum possible prime you need to check for any X?


  •  
    Winston Gutkowski
    Bartender
    Posts: 10777
    71
    Hibernate Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Now here I am going to go off-topic, but simply to confirm how wonderful prime numbers are.

    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.

    Winston
     
    Carey Brown
    Saloon Keeper
    Posts: 6923
    65
    Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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.
  • A count of all tests without the hint: 499,998,500,001
  • A count of tests needed with the hint: 89,357,989
  •  
    There's a way to do it better - find it. -Edison. A better tiny ad:
    Java file APIs (DOC, XLS, PDF, and many more)
    https://products.aspose.com/total/java
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!