**Question:**

Write a function that returns the list of all primes less than `n`.

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.

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.

- No even numbers are prime except for 2 are prime.
- 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.

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.

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

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

```
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!