Implementation of Sieve of Eratosthenes in Java

Question

I have implemented Sieve of Eratosthenes in Java as follows. Is there a way I can modify the below code to make it more efficient?

The current execution time is

0.8481224 seconds

import java.util.LinkedList;

public class LinkedListEx {

    public static void main(String[] args) {
        
        long startTime = System.nanoTime();

        LinkedList<Integer> ll = new LinkedList<Integer>();
        for(int i = 2; i< 10000; i++)
        {
            ll.add(i);
        }
        
        int ls = ll.size();
        
        for(int i=2; i < ls/2; i++)
        {
            for(int j =2; j<ls/2; j++)
            {
                int x = i*j;
                if(x<ls)
                    ll.remove(new Integer(x));
            }
            
            int y = i*i;

            if(y<ls)
                ll.remove(new Integer(y));
        }
        
        long endTime = System.nanoTime();
        
        double timeTakenToExecuteInSeconds = (double)(endTime - startTime)/1_000_000_000.0;
        
        System.out.println(ll);
        System.out.println(timeTakenToExecuteInSeconds);

    }
}

Answer 1

Datatype improvements

Of all the available Collection implementations, you chose to use LinkedList for your ll variable (by the way, candidatePrimes would be a better name). As you only use the add(Object) and the remove(Object) method, any Collection will do. So, you have the freedom to select one of (to name a few popular classes)

• ArrayList
• LinkedList
• HashSet
• TreeSet

Your program makes heavy use of the remove() method. While the act of removing an entry from a linked list is cheap, finding the place in the list where this is to happen is a costly operation (proportional to the current length of the list).

If you profile your application, the tool will most probably point out the remove() calls to be the bottleneck.

A Collection better suited to your usage pattern would be a HashSet, as it can remove an element in mostly constant time.

You might want to experiment with other Collection implementations as well, but I guess HashSet will turn out to be the winner.

Your basic decision was to maintain a collection of the candidate primes, shrinking during the process. The more classical approach is to have a fixed-size boolean[] array where true at index n means that n is a (candidate) prime number. That makes the Sieve process faster as indexed array access is a very fast operation (faster than any remove() can ever be), but makes collecting the results more complicated and probably slower.

Algorithmic improvements

You should adjust your loops.

You can stop the inner loop earlier. As you're only interested in numbers up to 10000, there's no need to remove higher numbers from your collection. Your current code will iterate both i and j up to 4999, leading up to a product of 24990001. Instead, you can leave the inner loop as soon as the product exceeds 10000:

    for (int j = 2; i*j <= 10000; j++)

As Andrei showed in his answer, the inner loop also need not start with 2. It's enough to have it start with i, as cases with e.g. i=17 and j=3 have already been covered with i=3 and j=17. So, it can read

    for (int j = i; i*j <= 10000; j++)

The outer loop needs to count only up to the square root of the maximum number. Why? Inside your nested loops, you mark compound numbers as non-primes, with one factor being i, and the other being j. If e.g. i=987 and j=97, you'll mark the same number 96739 as non-prime that has already been covered with i=97 and j=987. The square root is just the point where the second factor gets smaller than the first one.

You only need to enter the inner loop if i is a prime (if i is currently contained in your collection). Why? Take e.g. i=15. It's the product of 3 and 5. So, any multiple of 15 is also a multiple of 3 (and of 5), and all multiples of 3 have already been eliminated in the i=3 iteration. So, checking the multiples of 15 is a waste of time.

As we already know, multiples of 2 aren't primes, and you can easily put that knowledge into your program by a more elaborate initialization of your collection. Replace

    for(int i = 2; i< 10000; i++)
    {
        ll.add(i);
    }

with

    ll.add(2);
    for(int i = 3; i< 10000; i+=2)
    {
        ll.add(i);
    }

explicitly adding the known prime 2 and all odd numbers to the initial collection. This way, your initial collection has only half the size.

Accordingly, you can adjust the outer and the inner loop to just iterate over the odd numbers (as all the even non-primes have already been covered in the initialization).

Regarding

        int y = i*i;

        if(y<ls)
            ll.remove(new Integer(y));

You can completely remove this code section. The resulting y numbers have already been covered in the nested loops, whenever j=i.

If you apply all these changes, you have to replace the collection-size-based limit ls with one that directly represents the maximum number you're interested in.

Program structure

You're doing everything inside main(). It's better to have calculations and input/output in separate places. You should introduce a method

private static Collection<Integer> findPrimes(int maxNumber) { ... }

where you put the Sieve algorithm, and call that from main() where you do the results output and the timing.

And, please rename your class from LinkedListEx to something like EratosthenesPrimes. Don't name classes after implementation details, but after their purpose.

Answer 2

Initial benchmark with your implementation: 0.67s Just by changing linked list to array list: 0.14s

By replacing list implementations with an array: 0.0004s

The algorithm stays more or less the same, the difference is that the remove operation has O(1) complexity instead of O(n).

public class Main {

     public static void main(String[] args) {
        final int LENGTH = 10000;

        long startTime = System.nanoTime();

// initialization
        int[] arr = new int[LENGTH];
        for (int i = 2; i < LENGTH; i++) {
            arr[i - 2] = i;
        }

// iteration
        for (int i = 2; i < LENGTH / 2; i++) {
// if number has been removed continue to next number
            if (arr[i] == 0) continue;

// multiply until you reach the length
            for (int j = 2; i * j < LENGTH; j++) {
                int product = i * j;
                arr[product - 2] = 0;
            }
// no need to remove the square because it gets removed in the loop above
        }

        long endTime = System.nanoTime();

        double timeTakenToExecuteInSeconds = (double) (endTime - startTime) / 1_000_000_000.0;

        System.out.println(Arrays.toString(extractResult(arr)));
        System.out.println(timeTakenToExecuteInSeconds);

    }

    private static int[] extractResult(int[] arr) {
        int length = 0;

        for (int j : arr) {
            if (j != 0) length++;
        }

        int[] result = new int[length];
        for (int arrI = 0, resultI = 0; resultI < length; arrI++) {
            if (arr[arrI] != 0) {
                result[resultI] = arr[arrI];
                resultI++;
            }
        }

        return result;
    }
}
```

Answer 3

One solution would be to change LinkedList to ArrayList and change the second loop that uses j variable to start from i as solutions 2 to i were already checked.

This solution improved execution time from 0.67 sec to 0.09 sec:

import java.util.LinkedList;
import java.util.ArrayList;

public class LinkedListEx {

    public static void main(String[] args) {
        
        long startTime = System.nanoTime();

        List<Integer> ll = new ArrayList<Integer>(10100);
        for(int i = 2; i< 10000; i++)
        {
            ll.add(i);
        }
        
        int ls = ll.size();
        
        for(int i=2; i < ls/2; i++)
        {
           // start from i
            for(int j =i; j<ls/2; j++)
            {
                int x = i*j;
                if(x<ls)
                    ll.remove(new Integer(x));
            }
            
            int y = i*i;

            if(y<ls)
                ll.remove(new Integer(y));
        }
        
        long endTime = System.nanoTime();
        
        double timeTakenToExecuteInSeconds = (double)(endTime - startTime)/1_000_000_000.0;
        
        System.out.println(ll);
        System.out.println(timeTakenToExecuteInSeconds);

    }
}

Answer 4

1. LinkedListEx ... Ex what? The one of the past?

2. Your placing of curly braces is inconsistent.

3. LinkedList<Integer> ll = new LinkedList<Integer>(); can be shortened to LinkedList<Integer> ll = new LinkedList<>(); with the diamond operator.

   Since Java 10 with var ll = new LinkedList<Integer>(); for local variables.

4. Is this ll or l1? Does it stand for lazy-loading? (No, I know, it doesn't. But it's clear what I mean, isn't it?)

5. If you don't need special methods of a sub-type (abstract) super-types are preferred as types for LHS values of an equation, especially if they are interfaces: Collection<Integer> ll = new LinkedList<>();

6. It's convention to let commands like for, if be followed by a space to be able to easily distinguish them from method invocations.

7. Operators like <, =, / usually are enclosed in spaces.

8. new Integer(int) and new Integer(String) are deprecated since Java 9. "The static factory valueOf(int) is generally a better choice". "Use parseInt(String) to convert a string to a int primitive, or use valueOf(String) to convert a string to an Integer object."

9. There's TimeUnit since Java 1.5 for elegant time unit conversions.

10. 1_000_000_000.0 is a magic number. A final with a descriptive name would be better. But see the point before anyway.

11. Two System.out.println()s can be combined in a System.out.printf("%d%n%f", ll, timeTakenToExecuteInSeconds)

Answer 5

Anything involving Integer rather than int will have boxing and unboxing costs.

Anything involving remove() will have structure maintenance costs.

I'm not able to do a worked example right now, but I'd be surprised if anything beats an solution using https://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html

Update: I've tried, and the BitSet is fairly fast, but a simple boolean array seems better from my timings.

I note that some of the versions posted have some subtle bugs (and claim 169 and 301 as prime), but I'm fairly confident my solution is accurate.

I've avoided Wrapper classes, to avoid the boxing/unboxing costs, and used a boolean to mark a candidate number as known to be non-prime.

I thought that the numbering fell more comfortably without subtracting some offset, so made my array one entry larger than absolutely necessary.

import java.util.Arrays;

public class Sieve {

  private static final int NANOS_PER_SECOND = 1000_000_000;

  /*
   * [0] : ignored - allows us to do 1-based indexing cleanly
   * [n] : set if that integer is now known to be non-prime
   */
  private static boolean[] knownNonPrimes;

  private static int max;
  private static int maxFactor;

  public static void main(String[] args) {
    max = Integer.getInteger("Max", 10000);
    maxFactor = (int) Math.ceil(Math.sqrt(max)); // only need to check to root(max)
    knownNonPrimes = new boolean[max + 1]; // initially all false
    knownNonPrimes[0] = true; // zero is special
    markMultiples(2); // Special-case, to save checking other even numbers

    long startTime = System.nanoTime();
    int[] foundPrimes = findPrimes();
    long endTime = System.nanoTime();

    System.out.format("Time taken = %f seconds%n", 
      (double) (endTime - startTime) / NANOS_PER_SECOND);
    System.out.println(foundPrimes.length);
    System.out.println(Arrays.toString(foundPrimes));
  }

  private static int[] findPrimes() {
    for (int factor = 3; factor <= maxFactor; factor += 2) {
      // If we already know this is non-prime, 
      // then its multiples have been marked already
      if (!knownNonPrimes[factor]) {
        markMultiples(factor);
      }
    }

    int resultSize = 0;
    for (boolean knownNonPrime : knownNonPrimes) {
      if (!knownNonPrime) {
        resultSize += 1;
      }
    }
    int[] result = new int[resultSize];
    int resultIndex = 0;
    for (int primeCandidate = 1; primeCandidate <= max; primeCandidate++) {
      if (!knownNonPrimes[primeCandidate]) {
        result[resultIndex++] = primeCandidate;
      }
    }
    return result;
  }

  private static void markMultiples(int factor) {
    for (int multiple = factor * 2; multiple <= max; multiple += factor) {
      knownNonPrimes[multiple] = true;
    }
  }

}