Write a function to return all prime numbers up to a given number n.
Medium
Write a function find_primes(n) that returns all prime numbers less than or equal to n.
Examples
Pythonfind_primes(1) # => [] find_primes(5) # => [2, 3, 5] find_primes(20) # => [2, 3, 5, 7, 11, 13, 17, 19]
Solving mathematical problems like these can be tricky—often there is a specific piece of knowledge that you need to unlock the best solution.
In this case, we have to think carefully about the special properties of prime numbers: we know that a prime number cannot be divided by other numbers. With this knowledge alone, we can implement a brute force solution to the problem that finds all numbers, but this solution is computationally intensive with O(n^2) runtime.
The key to finding a better solution is realizing that all numbers are either prime or divisible by prime numbers. You may remember this from math class as the prime factorization of a number. For example, the prime factorization of 100 is 2 * 2 * 5 * 5. Now that we know this, we don't have to compare every pair of numbers, we can just compare our numbers to our list of primes so far.
But wait—there's an even faster solution, famously known as the Prime Sieve of Erastosthenes. Here's the basic idea: We create a boolean array prime of size n and initialize all entries to True. As we iterate through the array, we pre-compute all multiples and mark them as False (not prime). When we reach the end of the loop, we simply return all the remaining True values. This solution is faster but also uses O(n) memory.
