posted 3 years ago

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.

posted 3 years ago

1. Start checking divisors from 2 (instead of

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

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

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

posted 3 years ago

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.

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.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

posted 3 years ago

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?

Pawel Pawlowicz wrote:1. Start checking divisors from 2 (instead offorI - 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 inmainmethod.

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

posted 3 years ago

If you

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

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

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