• Post Reply Bookmark Topic Watch Topic
  • New Topic

Improving 10001st prime number project  RSS feed

 
Christopher McKay
Ranch Hand
Posts: 50
Android Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have been working on a Project Euler problem which is to find the 10001st prime number. I made the project in java and it gave me the correct answer (104743) . I couldn't help but notice that it had taken 17 seconds to find the answer. I am fairly new to java and I would appreciate feedback on how to improve the efficiency of my Java program - at the moment it is bruteforce.

 
Paweł Baczyński
Bartender
Posts: 2087
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
1. Start checking divisors from 2 (instead of forI - 1).
2. Check divisors up to sqrt(forI).
3. Apart from 2 don't try to divide by even number (if a number is even, it is not pime -- except for 2).
4. Check this: Sieve of Eratosthenes

On my PC calculating using your program took 19 seconds.
After I modified it acording to points 1, 2 and 3 (I didn't even try to implement the Sieve) it took... 23 milliseconds. It was almost 1000 times faster!

Apart from that:
Those variables should be declared in main method.

Also, consider writing isPime method. Your code would look cleaner and nicer.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think when I wrote mine, I saved every prime found so far. I then only divided by those up to the square root of the number...

update - once you solve a problem in Project Euler, you can read the discussion on the problem where many others discuss their solutions. The older problems are locked, so no new conversations are there, but you can learn a lot regardless.
 
Christopher McKay
Ranch Hand
Posts: 50
Android Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pawel Pawlowicz wrote:1. Start checking divisors from 2 (instead of forI - 1).
2. Check divisors up to sqrt(forI).
3. Apart from 2 don't try to divide by even number (if a number is even, it is not pime -- except for 2).
4. Check this: Sieve of Eratosthenes

On my PC calculating using your program took 19 seconds.
After I modified it acording to points 1, 2 and 3 (I didn't even try to implement the Sieve) it took... 23 milliseconds. It was almost 1000 times faster!

Apart from that:
Those variables should be declared in main method.

Also, consider writing isPime method. Your code would look cleaner and nicer.


Thank you, I managed to decrease the time it takes to 2.4 seconds so far. I had a bit of a problem when using sqrt. Here is my code, could you tell me where I could fit it in?

 
Campbell Ritchie
Marshal
Posts: 56578
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please note PP's suggestion to use a Sieve of Eratosthenes. I suspect you will find that much faster, even though it runs in quadratic time.
 
Paweł Baczyński
Bartender
Posts: 2087
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you really don't want to use the Sieve I strongly suggest that you write method with signature
boolean isPrime(int n)
When you do that you'll separate checking for primeness logic from counting primes logic.

In this method check if a number is smaller than 2. If so, it is not prime.
Else, check if a number is 2. If so, is is prime.
Else, check if a number is even. If so, it is not prime.
Else, loop from 3 to sqrt(n) adding 2 at every step and do modulo check. If you find any reminder == 0 then the number is not prime.
Return true after the loop.

You said I had a bit of a problem when using sqrt
What problem?

And you didn't listen to my suggestion that some variables SHOULD NOT be static variables inside your class. They belong to the method and should be declared inside main method.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!