Sieve of Eratosthenes optimization

Question

I am making a program to find primes between the given range of numbers. Unfortunately, the algorithm I created is too slow. Do you have any ideas of how to optimize the code?

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args)throws IOException {

        Scanner s = new Scanner(System.in);
        int numberOfTests;
        int l, n;
        numberOfTests = s.nextInt();

        for (int q = 0; q < numberOfTests; q++) {
            l = s.nextInt();
            n = s.nextInt();
            if (l==1)l++;
            BitSet primeBitSet = new BitSet((int) (Math.sqrt(n) + 1));
            ArrayList <Integer> primeTable = new ArrayList <Integer>((int) Math.sqrt(n));
            if (l < 1 || n < 1 || l > n || n > 1000000000) {
                System.exit(0);
            }

            //classic sieve from 1 to sqrt(n)
            for (int j = 2; j * j <= n; j++) {
                if (primeBitSet.get(j - 1) == true) {
                    continue;
                } else {

                    primeTable.add(j);
                    for (int k = 2 * j; k <= n; k += j) {
                        primeBitSet.set(k - 1);
                    }
                }
            }



            //sieve in the expected range using primes generated by the classic sieve
            BitSet primesInRangeBitSet = new BitSet(n - l + 1);
            int pomoc;
            for (int i = 0; i < primeTable.size(); ++i) {

                pomoc = l / ((int) primeTable.get(i));
                pomoc = pomoc * ((int) primeTable.get(i));
                for (int j = pomoc; j <= n; j = j + (int) primeTable.get(i)) {

                    if (j < l || primesInRangeBitSet.get(j - l) == true ) {
                        continue;
                    } else {
                        primesInRangeBitSet.set(j - l);
                    }
                }

            }

            //outputting the primes
            for (int k = 0; k < primeTable.size(); k++){
                if((int)primeTable.get(k)>= l &&(int) primeTable.get(k) <= n)
                    System.out.println(primeTable.get(k));
            }
            for (int k = 0; k < primesInRangeBitSet.size(); k++) {
                if (primesInRangeBitSet.get(k) == false && k <= n - l ) {
                    System.out.println((k + l));
                }
            }
            System.out.println("");
        }
    }
}

Answer 1

Variable scope

In order to make things easier to read/write, it is prefered to declare local variables as late as possible and in the smallest possible scope.

In your case, this holds for :

int numberOfTests = s.nextInt();

int l = s.nextInt();

int n = s.nextInt();

int pomoc = l / ((int) primeTable.get(i));

Also, BitSet primeBitSet can be declared just before the loop using it.

Continue

The way you use continue make things complicated for no obvious reasons.

            if (primeBitSet.get(j - 1) == true) {
                continue;
            } else {
                primeTable.add(j);
                for (int k = 2 * j; k <= n; k += j) {
                    primeBitSet.set(k - 1);
                }
            }

can be written :

            if (!primeBitSet.get(j - 1)) {
                primeTable.add(j);
                for (int k = 2 * j; k <= n; k += j) {
                    primeBitSet.set(k - 1);
                }
            }

New lines

The way you use new lines does not seem to make much sense. You should try to separate things into different "paragraphs".

After taking into accounts these comments about style, here's what the code would be like :

public class Main {

    public static void main(String[] args)throws IOException {
        Scanner s = new Scanner(System.in);
        int numberOfTests = s.nextInt();

        for (int q = 0; q < numberOfTests; q++) {
            int l = s.nextInt();
            int n = s.nextInt();
            if (l==1)l++;
            ArrayList <Integer> primeTable = new ArrayList <Integer>((int) Math.sqrt(n));
            if (l < 1 || n < 1 || l > n || n > 1000000000) {
                System.exit(0);
            }

            //classic sieve from 1 to sqrt(n)
            BitSet primeBitSet = new BitSet((int) (Math.sqrt(n) + 1));
            for (int j = 2; j * j <= n; j++) {
                if (!primeBitSet.get(j - 1)) {
                    primeTable.add(j);
                    for (int k = 2 * j; k <= n; k += j) {
                        primeBitSet.set(k - 1);
                    }
                }
            }

            //sieve in the expected range using primes generated by the classic sieve
            BitSet primesInRangeBitSet = new BitSet(n - l + 1);
            for (int i = 0; i < primeTable.size(); ++i) {
                int pomoc = (l / ((int) primeTable.get(i))) * ((int) primeTable.get(i));
                for (int j = pomoc; j <= n; j = j + (int) primeTable.get(i)) {
                    if (j >= l && !primesInRangeBitSet.get(j - l)) {
                        primesInRangeBitSet.set(j - l);
                    }
                }
            }

            //outputting the primes
            for (int k = 0; k < primeTable.size(); k++){
                if((int)primeTable.get(k)>= l &&(int) primeTable.get(k) <= n)
                    System.out.println(primeTable.get(k));
            }
            for (int k = 0; k < primesInRangeBitSet.size(); k++) {
                if (primesInRangeBitSet.get(k) == false && k <= n - l ) {
                    System.out.println((k + l));
                }
            }
            System.out.println("");
        }
    }
}

Algorithm

Now, this being said, there is a much bigger issue here. If tou want to implement Sieve of Eratosthene properly, everything you need is just a BitSet of size 1. If you really want to (but I don't really see the point), you can add primes numbers in a list as you detect them. If you just need to print them, you can print them as you detect them. In any case, I guess that from a performance point of view, it is not such a big deal to reiterate over the whole BitSet looking from prime numbers.

Answer 2

Firstly, let's take a look at minor issues:

1. Whenever you do a scanner.nextInt(), there is a possibility of exception been thrown when an invalid input is given. You should always check if a valid int value is available to read before actually reading it. So:

   int numberOfTests = s.nextInt();
   

   should be changed to:

   // Iterate till the next input is not an int
   while (!s.hasNextInt()) {
       // Consume this input, and discard it
       s.next();
   }
   // Read the next input, as it's an integer
   int numberOfTests = s.nextInt();
   

   Also, you might want to consider giving certain number of chances to pass valid integer value.

2. Similarly for the other two inputs you read in the for loop should be changed. Now you would sense some sort of code duplication there. What I would suggest is, create a static method, that reads an integer from user, and invoke it whenever you want an int value, and do the above stuff in that method:

   public static int readInt() {
       while (!scanner.hasNextInt()) {
           scanner.next();
       }
       return scanner.nextInt();
   }
   

   make sure to make the scanner a field of the class.

   And then replace that code in first point to:

   int numberOfTests = readInt();
   

3. The if condition in your code:

   if (primeBitSet.get(j - 1) == true)
   

   is always a bad idea of comparing boolean. It is better written as:

   if (primeBitSet.get(j - 1))
   

4. Note, I've changed the variable name from s to scanner. It makes more sense that way. You should really choose your variable names very cleverly. s and l are not really good variable names. They don't signify any meaning.

5. Also, you should try to minimize the scope of variables. l and n can be declared inside the for loop only. You aren't really using it outside.

Now, coming to the concrete issue, you don't seem to be following the algorithm correctly. In fact, you wouldn't need an ArrayList. The point of Sieve is, it just sets all the non-prime values to false in the given array of size n. And then finally, whatever index is set to true are primes. So you don't need to store the prime numbers separately. You can get them from that array only (In your case, it's a BitSet instead).

Given the value of l and n, just the below code should work fine:

Scanner scanner = new Scanner(System.in);
private static final int MAX_ATTEMPT = 3;

public static void main(String[] args) {

    int numberOfTests = readInt();

    for (int q = 0; q < numberOfTests; q++) {
        int start = readInt();
        int end = readInt();

        /* 
         * Create a BitSet of size `n`, and set all values from index 2 to end as true
         * assuming that all are primes. Index 0, and 1 are anyways not prime, so leave
         * them as false
         * Then in the course of moving along the algorithm,
         * we'll set all multiples of prime numbers to false
         */
        BitSet primeBitSet = new BitSet(end);
        primeBitSet.set(2, primeBitSet.size());

        // From index 2, run Sieve of Erathosthenes
        for (int j = 2; j < end; j++) {
            if (primeBitSet.get(j)) {
                    // This bit is set. That means this is prime. Set all multiples of 
                    // this bit as false
                for (int k = 2 * j; k < end; k += j) {
                    primeBitSet.set(k, false);
                }
            }
        }

        // Starting from `start`, print all the bits that are set
        for (int i = start; i < end; ++i) {
            if (primeBitSet.get(i)) {
                System.out.println(i);
            }
        }
    }

}

public static int readInt() {
    int attempt = 0;

    while (attempt < MAX_ATTEMPT && !scanner.hasNextInt()) {
        scanner.next();
        attempt++;
    }

    if (attempt == MAX_ATTEMPT) {
        // throw exception;
    }

    return scanner.nextInt();
}

Answer 3

I have to say it's really hard to follow your code. Why do you have no sub-methods? What does "pomoc" mean? Why do you use continue if flipping the condition would avoid it? And if (x == true)... can be written as if(x)...

An ArrayList can be slow because of boxing/unboxing, maybe a specialized structure is faster (e.g. from gnu-trove)

But the main questions is if you really use the correct algorithm. I can't tell without looking deeper, but if you're unsure, read "The Genuine Sieve of Eratosthenes" (it's Haskell, but you'll get the idea).

Note that from a theoretical point of view there are "faster" sieves, but I think they are much harder to implement, and it's hard to say if you really see a speed-up.

[Edit]

Based on @Rohit Jain's solution, special-casing the even numbers and skipping unnecessary tests:

    BitSet primeBitSet = new BitSet(end);
    primeBitSet.set(2, primeBitSet.size());

    for (int j = 4; j < end; j += 2) {
       primeBitSet.set(j, false);
    }
    for (int j = 3; j < end; j += 2) {
        if (primeBitSet.get(j)) {
            for (int k = j * j; k < end; k += 2*j) {
                primeBitSet.set(k, false);
            }
        }
    }

Answer 4

The sieve can also end when you reach the square root of your maximum index. This is because at that point, you will have marked out all of the non-primes in the BitSet and you can then use the BitSet as your list of primes. Of course, this assumes that you're not counting the primes as you go. If you are, then you'd have to go through the rest of the BitSet to count the other primes. Also, you say your code is 'too slow' but you don't say how fast it needs to be. This information would be helpful in creating an answer for you.