Generating a list of primes less than n

Related Tags:

What is a prime number?

A prime number is a whole number greater than 1, whose only two whole-number factors are 1 and itself. For example, the first few prime numbers are 2, 3, 5, 7, 11, 13, 17 and 19.

Properties of a prime number

In the brute force approach, we can take all values less than sqrt(n) and divide it by n. If we don't obtain an integer result, then that value is prime.

1. No even numbers are prime except for 2 are prime.
2. When determining whether a number n is prime or not, you only need to check values up to sqrt(n), since each composite above sqrt(n) has a corresponding prime factor less than or equal to that squareroot.

static boolean isPrime(int n) {
 
  if (num == 2) return true;
    if (n % 2 == 0) return false;
 
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
 
    return true;
}

This approach is correct, but extremely inefficient. Notice that it must iterate through all odd numbers less than our input value n.

Furthermore, obtaining a list of primes less than n would take exponential time since we must iterate through values each time. We could use memoization to avoid redundant calculations, but a better algorithm is the Sieve of Eratosthenes.

Sieve of Eratosthenes

The Sieve of Eratosthese is an algorithm that finds all prime numbers up to a given limit. Let's look at the algorithm pseudocode to see how this works.

Algorithm

1. Create a list of values from 1 to n.
2. Let p = 2, the first prime.
3. For each multiple of p, mark as false, denoting it is not a prime. Do not mark p itself as prime.
4. Repeat the last two steps up to but not including sqrt(n).
5. Now all the elements remaining must be prime.

Animation

Here's a great animation taken from Wikipedia that should help you understand what's going on.

Implementation in Java

import java.util.HashMap;

public class SieveOfEratosthenes {

	public static void main(String[] args) {

		findPrimes(120);

	}

	static ArrayList<Integer> findPrimes(int n) {

		// A key prime Integer will have a Boolean value of true.
		HashMap<Integer, Boolean> primeTable = new HashMap<>();

		// Load our table with values up to and including n.
		for (int i = 1; i <= n; i++) {
			primeTable.put(i, true);
		}

		// 1 is by definition not prime.
		primeTable.put(1, false);

		// For every value up to the sqrt(n).
		for (int i = 2; i * i < n; i++) {
			// If particular value is still set as prime
			// (otherwise those values will have already been covered.
			if (primeTable.get(i)) {

				// Set each multiple as not a prime 
				for (int p = i+i; p <= n; p += i) {
					primeTable.put(p, false);
				}
			}
		}

		// Now store all primes into a list and return
		ArrayList<Integer> primes = new ArrayList<>();	
		
		for (int i = 1; i <= primeTable.size(); i++) {
			if (primeTable.get(i))
				primes.add(i);
		}

		return primes;

	}
}

Came up with a better solution or have a question? Comment below!