Optimizing Sieve of Eratosthenes for larger numbers I am having difficulty optimizing my code for the Sieve of Eratosthenes. The code works fine for smaller numbers (up to 10,000) but takes a long time to run for numbers over 100,000.

import java.util.Arrays;
import java.util.Scanner;

public class SieveOfErasthostenes {

    static int num = 1; 
    static int count = 0;
    int i;
    static int nthPrime;

    public static void main(String[] args) {
        System.out.println("Enter the number of the prime: ");
        Scanner sc = new Scanner(System.in);
        nthPrime = sc.nextInt();
        long start = System.currentTimeMillis();
        boolean[] primes = new boolean[2*nthPrime*(int)Math.log(nthPrime)];
        Arrays.fill(primes,true);  
        primes[0]=primes[1]=false;       
        for (int i=2;i&lt;Math.sqrt(primes.length);i++) {
            while (count &lt; nthPrime){       
                num=num+1; //find the next prime number 
                for (i = 2; i &lt;= num; i++){         
                    if (num % i == 0) {         
                        break; //prime not found
                    }
                }
                if ( i == num){         
                    count = count+1; //prime found
                }
            }
        String th;
        if (nthPrime % 10 == 1) {
            th = "st";
        }   else if (nthPrime % 10 == 2) {
            th = "nd";
            }   else if (nthPrime % 10 == 3) {
                th = "rd";
            }   else {
                th = "th";
            }
        long elapsed = System.currentTimeMillis() - start;
        System.out.println("The " + nthPrime + th + " prime number is: " + num);
        System.out.println("Running time: " + elapsed);
        sc.close(); 
        }
    }   
}
Your question implies that you have a sieve of Erastosthenes, but you do not.

The sieve works from known-primes forward to a value with a given magnitude.

In other words, you start with a known prime (2), and then you eliminate all the multiples of 2 until you get to the end-point of the sieve. Then, you move forward from that known prime, to the next prime (which is the next number in your sieve that is prime). You then eliminate all multiples of that next prime too.

This ends up looking like a 2-stage process with a setup stage, and a double-loop stage.

Your code has a setup stage that is not used, and then has a three-loop structure that does things back-to-front.

The setup stage creates the sieve, which is a fixed size, that needs to 'cover' the 'nth' prime, wherever that may be. You may have to cover more than the exact value, which is why the formula 2*nthPrime*(int)Math.log(nthPrime) looks handy, but you should investigate this Wikipedia article about the approximate value of the Nth prime

So, once you have a large enough 'sieve', you then loop through it as follows:

for (int possiblePrime = 2; i &lt; sieve.size; possiblePrime++) {
    if (sieve[possiblePrime]) {
        for (int notPrime = possiblePrime * 2; notPrime &lt; sieve.size; notPrime += possiblePrime) {
            sieve[notPrime] = false;
        }
    }
}


Now, using those loops, you have a basic sieve of Eratosthenes, where all true values left in the sieve are primes. If the sieve is large enough, and you count them as you find them, then you can pull the Nth prime easily.

Note that the basic algorithm can be optimized in a bunch of ways.