programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Improving 10001st prime number project

Christopher McKay
Ranch Hand
Posts: 50
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
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
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
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
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
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.