Find prime numbers under N

This doesn't look like a Sieve of Eratosthenes. This sure looks like trial division:

 while(numbersIterator.hasNext()){ int number = numbersIterator.next(); if(number % prime == 0){ //Remove all multiples of the number. numbersIterator.remove(); } } 

Unless I'm misunderstanding what your iterators are doing. A simple SoE will have something that looks like:

for i from 2 to sqrt(n): /* Loop from 2 to square root of max */ if A[i]: /* If this location indicates prime, */ for j from i*i to n step i: /* then for each multiple of i, */ A[j] = false; /* mark composite */ 

See the examples at RosettaCode or Wikipedia for example. For comparison, RosettaCode's Trial Division task has a loop like your function.

So the immediate performance issue is that a sieve will be much faster than trial division.

There is a bug in your program; it doesn't print the number 2. Here is the problematic code:

int primeNumber = 2; //First prime number is 2 while(naturalNumbers.size() > 0){ primeNumber = naturalNumbers.pop(); 

• It may be preferred to just list the specific imports (not using *). It may not matter for this small program that uses a few, but it could be nicer to know exactly which imports are being used.

• Users of your code may want to know exactly which exceptions could be thrown. By just throwing Exception from main(), the user may just try to catch anything. I believe that Exception is put there by default with some IDEs (such as Ideone), while it doesn't imply that it'll always be needed, especially if the program won't potentially throw any exceptions.

  Basically, just remove it. If you know that main() could throw some exception (the compiler may alert you of the specific one at the specific location), then throw it.

• Since this while loop increments its counter each time:

  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++; } 

  it can just be a for loop:

  for (primeIndex = 1; naturalNumbers.size() > 0; primeIndex++) { primeNumber = naturalNumbers.pop(); //Always a prime since non-prime numbers are removed in the loop. System.out.println("Prime " + primeIndex + " : " + primeNumber); applyEratosthenesSieve(primeNumber, naturalNumbers); } 

First thing, I don't like the idea of building a list with all numbers. As @maaartinus pointed out in the comment, it's not necessary.

Secondly, I disagree with @DanaJ, trivial division is a primality test and not an algorithm to find all prime numbers up to a given limit. This looks like a variation of the "Sieve of Eratosthenes" (this algorithm "discards" composite numbers while the "Sieve of Eratosthenes" "marks" numbers as composite).

Also, I don't think there is the error @mjolka states because the code already comments that 2 is the first prime number. I just think that the following is missing before the loop:

System.out.println("Prime 0 : 2"); 

Following that,primeNumber could be declared inside the loop since the scope of local variables should always be the smallest possible.

And finally, is usually faster using a HashSet than Lists in Java because this class ensures constant time for basic operations like remove and contains (source)

The following example is a bit rough, I'm sure lots of optimizations could be made and that the presented algorithm is not the best one. But It shows the difference in performance between using a LinkedList and a HashSet. I've removed the System.out.println line from inside the loop and tried to make both alternatives as fair as possible.

And here is the code:

import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedList; import java.util.List; public class PrimeFinders { public static void main(String[] args) throws java.lang.Exception { for (int i=10; i <= 1000000; i*=10) { algorithmA(i); algorithmB(i); } } private static void algorithmA(int maxNumber) { LinkedList<Integer> naturalNumbers = new LinkedList<Integer>(); // 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 long time = System.currentTimeMillis(); while (naturalNumbers.size() > 0) { int primeNumber = naturalNumbers.pop(); // Always a prime since // non-prime numbers are // removed in the loop. applyEratosthenesSieve(primeNumber, naturalNumbers); primeIndex++; } long delta = (System.currentTimeMillis() - time); System.out.println("A Done in " + delta + "ms and primes found " + primeIndex + " for maxNumber " + maxNumber); } 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(); } } } private static void algorithmB(int maxNumber) { HashSet<Integer> primeNumbers = new HashSet<Integer>(maxNumber / 2); // Add only uneven numbers, as even numbers won't be prime for (int i = 3; i <= maxNumber; i += 2) { primeNumbers.add(i); } long time = System.currentTimeMillis(); for (int i = 3; i <= maxNumber; i +=2) { if (primeNumbers.contains(i)) { applyEratosthenesSieveB(i, primeNumbers, maxNumber); } } primeNumbers.add(2); // 2 is also a prime number // Sort prime numbers so this algorithm is "fair" with the other one List<Integer> primeNumbersOrdered = new ArrayList<Integer>(primeNumbers); Collections.sort(primeNumbersOrdered); long delta = (System.currentTimeMillis() - time); System.out.println("B Done in " + delta + "ms and primes found " + primeNumbersOrdered.size() + " for maxNumber " + maxNumber); } private static void applyEratosthenesSieveB(int prime, HashSet<Integer> numbers, int maxNumber) { // Remove all odd multiples of prime for (int x=2*prime; x <= maxNumber; x += prime) { numbers.remove(x); } } } 

Adding to @Boris answer (sorry that I cannot comment yet but I agree with almost everything):

I don't see any performance problems for computing such a small number of primes as the example in the question. Just follow the style and principle designs recommendations in these answers and that's it.

If we scale this algorithm to compute a large range of prime numbers and performance is really a concern, I would suggest the following:

1. We know even numbers (but 2) are composite, so we can modify @Boris' code to use less memory and be a bit faster if we only check for odd numbers. In a few words, we can allocate half the booleans and consider they're all odd (i.e.: 3, 5, 7, ...). The performance is better for a high target (if not is about the same) and consumes about half memory.

   List primesUpTo(final int target) {

   // 0,1 and 2 are not considered (-3) and even numbers neither (/2) // The inverse function is y = 2 * x + 3 final boolean[] nonPrime = new boolean[(target - 3) / 2]; for (int i = 0; i < Math.sqrt(nonPrime.length); i++) { if (!nonPrime[i]) { // We know that this position is a prime since still false int prime = 2 * i + 3; for (int j = i + prime; j < nonPrime.length; j += prime) { nonPrime[j] = true; } } } final List<Integer> primes = new ArrayList<>(); primes.add(2); // 2 is the first prime for (int i = 0; i < nonPrime.length; i++) { if (!nonPrime[i]) { int prime = 2 * i + 3; primes.add(prime); } } return primes; 

   }

2. For high performance algorithms, I don't think that using boolean or byte arrays is appropriate. First, in Java booleans are everything but 1 bit (their size is platform dependent) and it's usually faster to loop through a int since its size is 32 bits and how the JVM works. I would substitute this by a more complex solution with a int[] and using bit masks and bit operations. That would reduce memory to 1/4 (if we assume that 1 boolean is 8 bits). However, I'm confident that it would lead to a much faster and more optimized algorithm.

3. I would study about using multiple threads to speed it up.

4. If JNI is available, it's the way to go.

There are a lot of improvements possible, ranging from simple to very hard.

List of possible basic optimizations (no particular order, a few of these may have been covered in other answers):

1. Use booleans to store a simple yes/no answer, and the index for the number. For example, I could have an array of 1000 booleans, where true means a number at index i is composite and false means i is possibly prime (i.e. hasn't been sieved away yet).

1a. Improvement on 1 is to not use the boolean type, but do some direct bit twidling. A boolean usually takes 8 bits (1 byte) even though only 1 bit is needed for a true/false answer (I think in Java 7/8 they might have finally standardized it's size to 1 byte, but I don't know for sure). I didn't find a significant speed performance increase using this, but the 8x reduction in memory for the sieve is very helpful for going to large N. Have an array of ints/longs, and then index into these with bit twiddling to set/query it.

2. Don't use linked lists! Linked lists automatically means you'll miss out on cache coherency (it's a huge problem when you get into larger sieves). Use some array-type datastructure. For pure speed I recommend raw arrays, for clarity I recommend ArrayList. The reason arrays are much faster is because they don't have to play this auto boxing/unboxing game ArrayList does. There's about a 2x speedup for larger N. You can pre-allocate a space for storing found primes that's guaranteed to be large enough by using the equation: \$1.25506 * n / ln(n)\$.

3. The point of a sieve is that you never have to do a mod prime check; You simply start with every prime number in increasing order, and mark off multiples as not being prime. The next number larger than the current prime that hasn't been marked as not prime yet is guaranteed to be prime.

4. You only need to keep sieving until your sieving prime is greater than \$\sqrt{n}\$. Every number in your sieve after this that hasn't been marked as not prime is guaranteed to be prime.

5. For the outer sieve loop which finds the next valid prime you can either increment by 2, or implicitly ignore all even numbers in the sieve. Simply incrementing the outer loop by 2 has modest speedups (~10%), and implicitly ignoring all even numbers has a significant speedup, but your code does get more complicated (~50% speedup). Incidentally these methods roughly amount to a very small wheel factorization technique (more on this later).

Further reading of my results with associated code blocks:

Basic Sieve optimizations

Arrays vs. ArrayList Prime Sieve

The next big step is to implement segmented sieves and wheel factorization. The basic idea of segmented sieves is you only store part of the sieve in memory at a time and re-use it, leading to memory savings and more importantly very good cache usage. The idea of wheel factorization is to quickly mark of small primes "in bulk" from your sieve. Both of these are more advanced techniques, but they can provide good speedups.

My first attempts at a segmented sieve had an ~70% speedup over the non-segmented version: Simple Segmented Sieve

I also have a somewhat refined implementation of wheel factorization was able to get an additional ~40% speedup over my segmented sieve: wheel factorization sieve

I've made further improvements over the wheel factorization sieve, but this code switched to C++ and I don't remember exactly what I did (I didn't post this code online). I seem to recall that I was able to get this to run under 2 seconds for primes less than ~1 billion, possibly 1 second, but I can't remember for sure. Note that it wasn't switching to C++ which made my code automatically faster, but I made some actually algorithmic improvements to my code. Also, funny enough the biggest difference is my code ended up looking nicer because I had to play fewer of these funny tricks such as using raw arrays to avoid auto boxing/unboxing to get good performance.

The world record is currently held by primesieve. On roughly comparable hardware to mine, it is ~5x+ faster than my fastest implementation. I'm not entirely sure where he's able to get that much speedup over my code, but I haven't had enough time to look over his code and figure out what optimizations he's been able to make that I'm missing.

As far as programming style goes, quite a few of these optimizations lead to horrible looking code from a pure programming standpoint. Some of them can be cleaned up to look nicer, but many of them can't (for example, using raw arrays vs. ArrayList or all of the bit twiddling code). In these cases comments are your friends (unfortunately some of the posted links have good comments, and others don't)! I think the other answers do a decent job covering the other details of good coding style.

Also, Boris pointed out a key detail I would like to re-iterate on: benchmark your code often! You won't really know what changes will do to your performance unless you actually try them out. Some changes which theoretically sound like a good idea can give you terrible results. Other changes which seem like they shouldn't matter give unexpectedly large improvements in speed.

I see no advantage to using a linked list over an array. With an array you won't need to store the actual numbers since what you'll be checking for being prime is the INDEX, not the VALUE at the index. The VALUE at the index can be used to indicate whether the index is prime.

The most glaring thing I see in this is that after you find a prime you're iterating through the list by 1 to cast out all of the multiples of that prime. This is horribly wasteful of time since you can simply add a factor of twice your prime to reach the next number that is a multiple of your prime.

Also, iterating through the list each time by 1 to find the multiples of a known prime is not efficient. You know what the prime is, so just generate the multiples and throw them out. This eliminates any need for a division or modulus operation.