I'm using the Sieve of Eratosthenes to find primes numbers under N. Is there any performance problems you see with my approach? I used the LinkedList<Integer> because of the performance of removing items to the list while looping through it. Also, I'd want to know if I respect the Java conventions with my code.import java.util.*;import java.lang.*;import java.io.*;public class PrimeFinders{    public static void main (String[] args) throws java.lang.Exception    {        LinkedList<Integer> naturalNumbers = new LinkedList<Integer>();        final int maxNumber = 1000; //This is N        //Add only uneven numbers, as even numbers won't be prime        for(int i = 3; i <= maxNumber;i+=2){            naturalNumbers.add(i);        }        int primeIndex = 1; //Starting at 1 since we need to count the number 2, not added in the list        int primeNumber = 2; //First prime number is 2        while(naturalNumbers.size() > 0){            primeNumber = naturalNumbers.pop(); //Always a prime since non-prime numbers are removed in the loop.            System.out.println(Prime  + primeIndex +  :  + primeNumber);            applyEratosthenesSieve(primeNumber, naturalNumbers);            primeIndex++;        }    }    private static void applyEratosthenesSieve(int prime, LinkedList<Integer> numbers){        Iterator<Integer> numbersIterator = numbers.iterator();        while(numbersIterator.hasNext()){            int number = numbersIterator.next();            if(number % prime == 0){ //Remove all multiples of the number.                numbersIterator.remove();            }        }    }}
Find prime numbers under N
java;performance;beginner;primes;sieve of eratosthenes
You're close to a sieve, but you're missing some points.First and foremost your applyEratosthenesSieve is incorrect - this should step though the range in steps of prime; this very fact precludes the use of a LinkedList.The usual approach uses a boolean[] nonPrime , on which you carry out the following steps:Set everything to false as you don't know if anything is a composite. This isn't really required as in Java boolean is false by default.Starting with i = 2 to Math.sqrt(target), if !nonPrime[i], loop over nonPrime for j = i * 2 while j < nonPrime.length in increments of i and set nonPrime[j] = true.You now have an boolean[] where anything that is false (>=2) is a prime.The simplest implementation I can think of is:List<Integer> primesUpTo(final int target) {    final boolean[] nonPrime = new boolean[target + 1];    for (int i = 2; i <= Math.sqrt(target); ++i) {        if (!nonPrime[i]) {            for (int j = i * 2; j <= target; j += i) {                nonPrime[j] = true;            }        }    }    final List<Integer> primes = new ArrayList<>();    for (int i = 2; i <= target; ++i) {        if (!nonPrime[i]) primes.add(i);    }    return primes;}Using Caliper this method has a runtime of around 5ms for target=1,000,000.I have done a few experiments with speeding up the code. For example, using the Prime number theorem we know that there are approximately x/ln(x) prime numbers between 1 and x. Using this information we can create the ArrayList used for storing the primes to almost the right size:final int approxPiX = (int) (target / Math.log(target));final List<Integer> primes = new ArrayList<>(approxPiX);This should reduce the amount of time the ArrayList spends resizing itself. This reduces the runtime by about .1ms for target=1,000,000 - so has little effect. These sort of micro-optimisations should always be tested using benchmarks to see if the additional code complexity warrants their addition.A few comments on the code:Use of finalYou use final sometimes to delimit references that won't change:final int maxNumber = 1000;But not in other places:LinkedList<Integer> naturalNumbers = new LinkedList<Integer>();I don't like this. I think if you are going to down the route of using final then use it for all references that won't change, that includes:fieldsmethod parametersvariablesloop iteratorsScopeIt is generally good practice to scope variables in the minimum possible scope. I don't like this:int primeIndex = 1; //Starting at 1 since we need to count the number 2, not added in the listint primeNumber = 2; //First prime number is 2while(naturalNumbers.size() > 0){    primeIndex++;}Firstly because of the scope of primeXXX and also because loop indicies should be incremented inside a for declaration unless you have a good reason not to.I would prefer the following construct as it show that I have two variables used in the loop, that the termination condition is naturalNumbers.size() > 0 and that I increment primeIndex every iteration.for (int primeIndex = 1, primeNumber = 2; naturalNumbers.size() > 0; ++primeIndex) {}IteratorsKudos for correctly using an Iterator to remove() from a Collection while iterating. But, as described above, this is not the correct approach to implementing a Sieve.Programming to the interfaceI don't link this method declaration:private static void applyEratosthenesSieve(int prime, LinkedList<Integer> numbers){You don't use any of the properties of LinkedList. You do not need to know that it is a LinkedList. I would specify the argument as Iterable and leave the invoking class to decide on an implementation.BracketsThere are two styles of using curly brackets in Java, and either are valid:thing {    ...}thing{    ...}But (and this is a big one for style) you should only use one type. You have got one type in some places and the other type in other places. Set a preferred style in your IDE and stick to it. Also, if using Egyptian brackets (the first style) please leave a space between the statement and the opening bracket.CommentsComments like this:final int maxNumber = 1000; //This is NAre horrible! If you need to label a variable declaration with what that variable is, you have picked the wrong name.Further, if you are going to use inline comments, avoid the case where the comment makes the line so long that it's illegible.