Find primes faster (Java) I'm new here, and relatively new to coding. I wrote a method that returns an array of the n first primes. Even though my intended goal was just to find the nth prime, I ended up using an array (int[] primes) in order to minimize calculations.

My method goes iterates upwards by 2, since even numbers greater than 2 are not primes, and testing if the candidate number is a multiple of the previous primes (of course not including 2) that have been found up until the test. 

Actually it does not do that test with all the previous primes, only up to the square root of the last prime found. You can take a look at my method.

public int[] primes(int n){

    int[] primes = new int[n];
    primes[0] = 2;

    int count = 1;
    int number = 3;

    boolean numberIsPrime;

    while (count &lt; n){

        numberIsPrime = true;

        for (int i = 1; i &lt; (int)(Math.sqrt(number)); i++) {

            if (number % primes[i] == 0){
                numberIsPrime = false;
                break;
            }

        }

        if (numberIsPrime){

            primes[count] = number;
            count++;
        }

        number = number + 2;

    }

    return primes;

}


I tested it in a main method through System.out.println(instance.primes(n)[n-1]); for n = 1 million and it took not more than 10 seconds to find the correct answer, and for n = 10 million it took no more than 4 and a half minutes to find the correct answer. 

I let it run for n = 100 million, since I started writing this question, and it doesn't look like it is going to finish for an hour or so. I think mathematically I reduced calculations a lot.

Just by decreasing the test to the square root of the last prime did reduce computing time quite much. 

But can it be improved, not only mathematically but also by means of code?
Watch for mixed idioms


        for (int i = 1; i &lt; (int)(Math.sqrt(number)); i++) {



This is wasteful.  All you need to do is 

        for (int i = 1; primes[i] &lt;= (int)(Math.sqrt(number)); i++) {


This only works in that it always checks too many values.  i and number are not actually related here.  The comparative relation is between primes[i] and number.  This relies on i &lt; primes[i] for all i.  

And as noted in a comment, this puts a lot of reliance on the compiler to figure out that the square root will be constant.  Consider 

        int largestSmallerFactor = (int)(Math.sqrt(number));
        for (int i = 1; primes[i] &lt;= largestSmallerFactor; i++) {


Now it's clear that we only take the square root once.  

Helper method


        if (numberIsPrime){



Consider 

        if (isOddPrime(number, primes)) {


Then you just need a helper method and can get rid of numberIsPrime altogether.  

private boolean isOddPrime(int candidate, int[] primes) {
    int largestSmallerFactor = (int)(Math.sqrt(candidate));
    for (int i = 1; primes[i] &lt;= largestSmallerFactor; i++) {
        if (candidate % primes[i] == 0) {
            return false;
        }
    }

    return true;
}


Optimization

Perhaps you are concerned that a method call has too much overhead.  If so, consider 

    nextCandidate:
    while (count &lt; n) {
        int largestSmallerFactor = (int)(Math.sqrt(number));
        for (int i = 1; primes[i] &lt;= largestSmallerFactor; i++) {
            if (number % primes[i] == 0) {
                continue nextCandidate;
            }
        }

        primes[count] = number;
        count++;
    }


No method overhead.  

People will point out that the method is a more readable and robust solution, which it is.  But if you're trying to wring out every possible efficiency, this might be better.  You'd have to compile and compare both versions to see.  Remember that the compiler might have an even better optimization for the method version.  

Sieve of Eratosthenes

A comment suggested using the Sieve of Eratosthenes.  While it is true that that's an efficient way to find primes, it is not well suited to finding the nth prime.  The problem is that it checks a certain number of numbers, so there is a tendency to either overshoot or undershoot.  

You can use a segmented sieve to process the sieve partially.  So if you undershoot, you can continue.  This also allows you to make smaller jumps, so you are less likely to overshoot.  

It was asserted that a sieve avoids repeated division.  That's true but it replaces it with redundant multiplication.  For example, 210 is marked as not prime by the sieving operations for 2, 3, 5, and 7.  Or more generally, a number divisible by 6 will be sieved by both 2 and 3.  By contrast, trial division can stop as soon as it finds the first factor.  

It may be that the sieve is faster on average.  After all, a square root is an expensive operation.  But it can do more work for a particular number than trial division does.  

Here is an example of a windowed sieve which you could try to modify to this purpose.  Don't forget to time it both ways.