Home
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.
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.
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!
Next Challenge: Cheryl's Birthday