3
\$\begingroup\$

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<Math.sqrt(primes.length);i++) {
            while (count < nthPrime){       
                num=num+1; //find the next prime number 
                for (i = 2; i <= 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(); 
        }
    }   
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Calculate nthPrime % 10 only once and compare that result with 1, 2 and 3. Also, that primes array seems to be meaningless, since you're not using it, except for his length. \$\endgroup\$ – Tom Nov 10 '14 at 20:00
  • 3
    \$\begingroup\$ I cannot see how this program implements the Sieve of Eratosthenes. It does a "brute-force" search for the n-th prime by testing each candidate for all possible divisors. \$\endgroup\$ – Martin R Nov 10 '14 at 20:14
5
\$\begingroup\$

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 < sieve.size; possiblePrime++) {
    if (sieve[possiblePrime]) {
        for (int notPrime = possiblePrime * 2; notPrime < 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.

\$\endgroup\$
0
3
\$\begingroup\$

Since you're not using the primes for something necessary, you can remove it. This would also get rid of the Arrays.fill(primes,true); call and you don't need to "waste" your memory with it.

You're calling Math.sqrt(primes.length) on each for iteration. Calculating that can take same time and since the result won't change, do to the immutable argument, it is better to calculate that value just once and use that result in the for loop:

final double result = Math.sqrt( 2 * nthPrime * (int)Math.log(nthPrime) );
for (int i = 2; i < result; i++) {
    // ...
}

This if/else block:

if (nthPrime % 10 == 1) {
    th = "st";
} else if (nthPrime % 10 == 2) {
    th = "nd";
} else if (nthPrime % 10 == 3) {
    th = "rd";
} else {
   th = "th";
}

can be slitely improved by extracting the nthPrime % 10 calculation to do it only once and not three times.

 int firstDigit = nthPrime % 10;
 if (firstDigit == 1) {
     th = "st";
 } else if (firstDigit == 2) {
     th = "nd";
 } else if (firstDigit == 3) {
     th = "rd";
 } else {
    th = "th";
 }

And now a small "thought experiment": This for loop:

for (i = 2; i <= num; i++){         
     if (num % i == 0) {         
          break; //prime not found
     }
}

maybe could be improved by doing some basic checks with num before performing this loop. For example test if the first digit is even and therefore divisible by 2. Or check if the sum of nums digits is divisible by 3, to prove that num itself is divisible by 3. This might or might not improve the performance, but it is an interesting task to test the performance of this :).

\$\endgroup\$
3
  • 3
    \$\begingroup\$ "Or check if the sum of nums digits is divisible by 3, to prove that num itself is divisible by 3" – I strongly assume that computing num % 3 is much faster than computing the sum of the digits first. \$\endgroup\$ – Martin R Nov 10 '14 at 20:31
  • \$\begingroup\$ @MartinR That is right and the first check of this for is the check of an even or odd number. That is why, I'm not sure that my idea might improve the performance or not. There are some doubts :D. \$\endgroup\$ – Tom Nov 10 '14 at 20:36
  • \$\begingroup\$ Nicely done! +1 \$\endgroup\$ – janos Nov 11 '14 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.