find nth prime number

Question

I've written the following code below to find the nth prime number. Can this be improved in time complexity?

Description:

The ArrayList arr stores the computed prime numbers. Once arr reaches a size 'n', the loop exits and we retrieve the nth element in the ArrayList. Numbers 2 and 3 are added before the prime numbers are calculated, and each number starting from 4 is checked to be prime or not.

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>(); // stores prime numbers 
                                                      // calculated so far
    // add prime numbers 2 and 3 to prime array 'arr'
    arr.add(2); 
    arr.add(3);

    // check if number is prime starting from 4
    int counter = 4;
     // check if arr's size has reached inp which is 'n', if so terminate while loop
    while(arr.size() <= inp) {
        // dont check for prime if number is divisible by 2
        if(counter % 2 != 0) {
            // check if current number 'counter' is perfectly divisible from 
           // counter/2 to 3
            int temp = counter/2;
            while(temp >=3) {
                if(counter % temp == 0)
                    break;
                temp --;
            }
            if(temp <= 3) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp));
    }
}

Solution 1

Yes.

Your algorithm make O(n^2) operations (maybe I'm not accurate, but seems so), where n is result.

There are http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes algorithm that takes O(ipn* log(log(n))). You can make only inp steps in it, and assume that n = 2ipn*ln(ipn). n just should be greater then ipn-prime. (we know distributions of prime numbers http://en.wikipedia.org/wiki/Prime_number_theorem)

Anyway, you can improve existing solution:

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    arr.add(2);
    arr.add(3);

    int counter = 4;

    while(arr.size() < inp) {
        if(counter % 2 != 0 && counter%3 != 0) {
            int temp = 4;
            while(temp*temp <= counter) {
                if(counter % temp == 0)
                    break;
                temp ++;
            }
            if(temp*temp > counter) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp-1));
    }
}

Solution 2

A few things you can do to speed it up:

1. Start counter at 5 and increment it by 2 instead of 1, then don't check mod 2 in the loop.
2. Instead of starting temp at counter / 2, start it at the first odd <= int(sqrt(counter))
3. decrement temp by 2.

I'm not sure whether it counts as improving complexity, but (2) above will go from O(n^2) to O(n*sqrt(n))

Comments

[codewarrior]

could you tell me how this works, specifically why do you check using temp*temp? thats going to check if the counter is divisible by 16,25,36..

[G. Bach]

He checks temp*temp against counter since that implies that temp <= sqrt(counter). It's enough to check up to that point since multiplication is commutative.

[Will Ness]

what is n? what is ipn? Is inp inp? Is this the Sieve of Eratosthenes?

[Will Ness]

testing by temp from the sqrt down is very inefficient. I suspect it even changes the complexity for the worse.

[Daniel Fischer]

@Will It does indeed. I haven't analysed it in detail, but the semiprimes whose larger factor is at least four times the smaller factor alone give an additional log log n factor. I expect that the constant factor slowdown is much worse for a long long time, though.

[Will Ness]

@Daniel empirically ideone.com/iNxOrC indeed the counting-down code seems to run in m^1.5, where m is the top limit. The ratios of actual run times are 2.6x ... 3.6x and worsening, for top limit 100k ... 1.2mln. m^1.5 for counting-down code actually makes sense - there's no early cut-off so it's as if testing each odd by all odds below sqrt. While in counting-up the cost for non-prime odds is at the most the same as for primes (as shows M. O'Neill), giving the m^1.5/log(m).

[Daniel Fischer]

@Will What do you mean with "early cut-off"? You divide until you find the first divisor or hit the limit, whether you count up or down, in that respect, both ways are similar. Counting down, you generally have a much longer way to the first divisor, though. I sort-of expect it to be Θ(√n) on average (so the empirical m^1.5 fits), but I don't see an easy way to prove it (closest divisor to √n is harder to grip than smallest prime divisor).

[Will Ness]

@Daniel that's what I meant, yes, the much longer way is almost "all the way". It is of course not rigorous in any way. Try finding the "expected value" of biggest factor for a randomly-chosen composite in the range 2..n, something to that effect (it will be our cut-off point, on average, counting down). n or sqrt(n), I expect won't make much of a difference.

[Will Ness]

@Daniel ouch. how stupid of me. of course it must be greatest factor of i below sqrt i for i<-[2..n].

[Keegan]

Don't you need to add 1 to arr? Otherwise asking for the first prime number yields 2 instead of 1.

[xvorsx]

Keegan, prime numbers start from 2. en.wikipedia.org/wiki/Prime_number#Definition_and_examples

[zbarker]

Can you include an indication of the improvement?

[greybeard]

How does this [improve] time complexity [of find the nth prime over counting primes identified by trial division]?

[Admin]

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.