Prime Numbers
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]
A prime number is defined as any number that cannot be evenly divided by any other number.
Once we've found a prime number, what else do we know? For example, we know 2 is the only even prime number because all others are multiples of 2.
Could we pre-compute the multiples of prime numbers we've found so far?
Does your solution run in O(n^2) time? Can you make it faster?
Do you perform any extra computations that can be optimized?
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.
# Solution 1: Memoize primes discovered so far
def find_primes(n):
primes = []
i = 2
while i <= n:
prime = True
for p in primes:
if i % p == 0:
prime = False
break
if prime:
primes.append(i)
i += 1
return primesBut 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.
# Solution 2: "Prime sieve" that pre-computes multiples of primes
def find_primes(n):
prime = [True for i in range(n+1)]
i = 2
while (i * i <= n):
if prime[i]:
for j in range(i*i, n+1, i):
prime[j] = False
i += 1
return [j for j in range(2, n+1) if prime[j]]
def test_find_primes():
assert find_primes(1) == []
assert find_primes(20) == [2, 3, 5, 7, 11, 13, 17, 19]
test_find_primes()
def find_primes(n): lst=[] for i in range(2,n+1): is_prime=1 for j in range(2,int(i**0.5)+1): if i%j==0: is_prime=0 break if is_prime: lst.append(i) return lst