Improving 10001st prime number project

[Christopher McKay]

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.

static boolean isPrime;
	static int primeCount;
	static int forI = 1;
	static int latestPrime;
	public static void main(String[] args){
		long startTime = System.currentTimeMillis();
		while(primeCount < 10001){
			isPrime = true;
			forI++;
			for(int i = forI - 1; i > 1; i--){
				//If forI is divisible by another number < forI, it is not prime
				if(forI % i == 0){
					isPrime = false;
				}
			}
			if(isPrime){
				primeCount++;
				latestPrime = forI;
			}
		}
		long endTime = System.currentTimeMillis() - startTime;
		System.out.println(primeCount+" "+latestPrime);
		System.out.println("Time taken: " + endTime / 1000 + " seconds");
	}

[Paweł Baczyński]

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:

static boolean isPrime;  
static int primeCount;  
static int forI = 1;  
static int latestPrime;

Those variables should be declared in main method.

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

[fred rosenberger]

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]

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:

static boolean isPrime;  
static int primeCount;  
static int forI = 1;  
static int latestPrime;

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?

static boolean isPrime;
	static int primeCount;
	static int forI = 1;
	static int latestPrime;
	public static void main(String[] args){
		long startTime = System.currentTimeMillis();
		while(primeCount < 10001){
			isPrime = true;
			forI++;
			for(int i = 2; i < forI; i++){
				//If forI is divisible by another number < forI, it is not prime
				if(forI % 2 == 0 && forI != 2){
					isPrime = false;
					break;
				}
				if(forI % i == 0){
					isPrime = false;
					break;
				}
			}
			if(isPrime){
				primeCount++;
				latestPrime = forI;
			}
		}
		long endTime = System.currentTimeMillis() - startTime;
		System.out.println(primeCount+" "+latestPrime);
		System.out.println("Time taken: " + (double) endTime / 1000 + " seconds");
	}

[Campbell Ritchie]

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]

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.